  We study the problem of finding a Euclidean minimum weight perfect matching
for $n$ points in the plane. It is known that a deterministic approximation
algorithm for this problems must have at least $\Omega(n \log n)$ runtime. We
propose such an algorithm for the Euclidean minimum weight perfect matching
problem with runtime $O(n\log n)$ and show that it has approximation ratio
$O(n^{0.2995})$. This improves the so far best known approximation ratio of
$n/2$. We also develop an $O(n \log n)$ algorithm for the Euclidean minimum
weight perfect matching problem in higher dimensions and show it has
approximation ratio $O(n^{0.599})$ in all fixed dimensions.
