Compatible Geometric Matchings - Mathematics > CombinatoricsReportar como inadecuado

Compatible Geometric Matchings - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.

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


Documentos relacionados