Euclidean Maximum Matchings in the Plane---Local to Global

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'=₁b₁,,aₖbₖ\ of k edges of M it holds that $M'$ is a maximum-length matching on points ₁,b₁,,aₖ,bₖ\. We show that local maximum matchings are good approximations of global ones. Let μₖ 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-1/k for any k 2. We show the following improved bounds for k∈\2,3\: √3/7μ₂< 0.93 and √3/2μ₃< 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 μ₂ 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.