2024/05/30 by Ahmad Biniaz, Biniaz, Ahmad, Anil Maheshwari +3
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2405.20424
openalex publication_date 2024/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let M be a perfect matching on a set of points in the plane where every edge is a line segment between two points. We say that M is globally maximum if it is a maximum-length matching on all points. We say that M is k-local maximum if for any subset M'=\a1b1,…,akbk\ of k edges of M it holds that M' is a maximum-length matching on points \a1,b1,…,ak,bk\. We show that local maximum matchings are good approximations of global ones. Let μk be the infimum ratio of the length of any k-local maximum matching to the length of any global maximum matching, over all finite point sets in the Euclidean plane. It is known that μk\geqslant (k-1)/(k) for any k\geqslant 2. We show the following improved bounds for k∈\2,3\: √(3/7)\leqslantμ2< 0.93 and √(3)/2\leqslantμ3< 0.98. We also show that every pairwise crossing matching is unique and it is globally maximum. Towards our proof of the lower bound for μ2 we show the following result which is of independent interest: If we increase the radii of pairwise intersecting disks by factor 2/√(3), then the resulting disks have a common intersection.