  In this work, we study the parallel complexity of the Euclidean
minimum-weight perfect matching (EWPM) problem. Here our graph is the complete
bipartite graph $G$ on two sets of points $A$ and $B$ in $\mathbb{R}^2$ and the
weight of each edge is the Euclidean distance between the corresponding points.
The weighted perfect matching problem on general bipartite graphs is known to
be in RNC [Mulmuley, Vazirani, and Vazirani, 1987], and Quasi-NC [Fenner,
Gurjar, and Thierauf, 2016]. Both of these results work only when the weights
are of $O(\log n)$ bits. It is a long-standing open question to show the
problem to be in NC.
  First, we show that for EWPM, a linear number of bits of approximation is
required to distinguish between the minimum-weight perfect matching and other
perfect matchings. Next, we show that the EWPM problem that allows up to
$\frac{1}{poly(n)}$ additive error, is in NC.
