A bottleneck plane perfect matching of a set of n points in ℝ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 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 (formula presented.) in O(n log2 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 (formula presented.) whose edges have length at most (formula presented.) the bottleneck.

Additional Metadata
Keywords Approximation algorithm, Bottleneck matching, Geometric graph, Plane matching, Unit disk graph
Persistent URL dx.doi.org/10.1016/j.comgeo.2015.06.005
Journal Computational Geometry
Citation
Abu-Affash, A.K. (A. Karim), Biniaz, A. (Ahmad), Carmi, P. (Paz), Maheshwari, A, & Smid, M. (2015). Approximating the bottleneck plane perfect matching of a point set. Computational Geometry, 48(9), 718–731. doi:10.1016/j.comgeo.2015.06.005