Approximating the bottleneck plane perfect matching of a point set

作者：Abu Affash A Karim; Biniaz Ahmad^*; Carmi Paz; Maheshwari Anil; Smid Michiel

来源：Computational Geometry-Theory and Applications, 2015, 48(9): 718-731.

DOI：10.1016/j.comgeo.2015.06.005

• Plane matching
• Bottleneck matching
• Geometric graph
• Unit disk graph
• Approximation algorithm

A bottleneck plane perfect matching of a set of n points in 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 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 n/5 in O(n log(2)n)-time. Then we extend our idea toward an O(n logn)-time approximation algorithm which computes a plane matching of size at least 2n/5 whose edges have length at most root 2 + root 3 times the bottleneck.

• 出版日期2015-10