错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Euclidean Maximum Matchings in the Plane—Local to Global

  • Ahmad Biniaz,
  • Anil Maheshwari,
  • Michiel Smid

摘要

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'=\{a_1b_1,\dots ,a_kb_k\}\) M = { a 1 b 1 , , a k b k } of k edges of M it holds that \(M'\) M is a maximum-length matching on points \(\{a_1,b_1,\dots ,a_k,b_k\}\) { a 1 , b 1 , , a k , b k } . We show that local maximum matchings are good approximations of global ones. Let \(\mu _k\) μ 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 \(\mu _k\geqslant \frac{k-1}{k}\) μ k k - 1 k for any \(k\geqslant 2\) k 2 . We show the following improved bounds for \(k\in \{2,3\}\) k { 2 , 3 } : \(\sqrt{3/7}\leqslant \mu _2< 0.93 \) 3 / 7 μ 2 < 0.93 and \(\sqrt{3}/2\leqslant \mu _3< 0.98\) 3 / 2 μ 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 \(\mu _2\) μ 2 we show the following result which is of independent interest: If we increase the radii of pairwise intersecting disks by factor \(2/\sqrt{3}\) 2 / 3 , then the resulting disks have a common intersection.