Compatible Geometric Matchings - Mathematics > CombinatoricsReport as inadecuate

Compatible Geometric Matchings - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: This paper studies non-crossing geometric perfect matchings. Two such perfectmatchings are \emph{compatible} if they have the same vertex set and theirunion is also non-crossing. Our first result states that for any two perfectmatchings $M$ and $M-$ of the same set of $n$ points, for some $k\in\Oh{\logn}$, there is a sequence of perfect matchings $M=M 0,M 1,

.,M k=M-$, such thateach $M i$ is compatible with $M {i+1}$. This improves the previous best boundof $k\leq n-2$. We then study the conjecture: \emph{every perfect matching withan even number of edges has an edge-disjoint compatible perfect matching}. Weintroduce a sequence of stronger conjectures that imply this conjecture, andprove the strongest of these conjectures in the case of perfect matchings thatconsist of vertical and horizontal segments. Finally, we prove that everyperfect matching with $n$ edges has an edge-disjoint compatible matching withapproximately $4n-5$ edges.

Author: Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, Mikio Kano, Alberto Márquez,


Related documents