Approximating the bottleneck plane perfect matching of a point set
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.
|Keywords||Approximation algorithm, Bottleneck matching, Geometric graph, Plane matching, Unit disk graph|
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