A bottleneck plane perfect matching of a set of $n$ points in $\mathbb{ R}^2$ is defined to be a perfect non-crossing matching that minimizes the length of the longest edge; the length of this longest edge is known as { \em bottleneck}. The problem of computing a bottleneck plane perfect matching has been proved to be NP-hard. We present an algorithm that computes a bottleneck plane matching of size at least $\frac{ n}{ 5}$ in $O(n \log^2 n)$-time. Then we extend our idea toward an $O(n\log n)$-time approximation algorithm which computes a plane matching of size at least $\frac{ 2n}{ 5}$ whose edges have length at most $\sqrt{ 2}+\sqrt{ 3}$ times the bottleneck.
Categories: cs.CG