2007/09/30 by Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu +14 · 1 citation
Computer Science · Engineering · Mathematics · #3D Shape Modeling and Analysis #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #math.CO #msc:52C99
paper · pdf · doi:10.1016/j.comgeo.2008.12.005
published as Computational Geometry: Theory & Applications 42(6-7):617-626, 2009. · improved exposition and improved results
arxiv created 2008/01/16 · openalex publication_date 2009/01/08 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03
This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are compatible if they have the same vertex set and their union is also non-crossing. Our first result states that for any two perfect matchings M and M' of the same set of n points, for some k∈\Ohlog n, there is a sequence of perfect matchings M=M0,M1,...,Mk=M', such that each Mi is compatible with Mi+1. This improves the previous best bound of k≤ n-2. We then study the conjecture: every perfect matching with an even number of edges has an edge-disjoint compatible perfect matching. We introduce a sequence of stronger conjectures that imply this conjecture, and prove the strongest of these conjectures in the case of perfect matchings that consist of vertical and horizontal segments. Finally, we prove that every perfect matching with n edges has an edge-disjoint compatible matching with approximately 4n/5 edges.