Compatible Geometric Matchings

Simple item page
dc.creatorAichholzer, Oswin
dc.creatorBereg, Sergey
dc.creatorDumitrescu, Adrian
dc.creatorGarcía, Alfredo
dc.creatorHuemer, Clemens
dc.creatorHurtado, Ferran
dc.creatorKano, Mikio
dc.creatorMárquez, Alberto
dc.creatorRappaport, David
dc.creatorSmorodinsky, Shakhar
dc.creatorSouvaine, Diane
dc.creatorUrrutia, Jorge
dc.creatorWood, David R.
dc.date2007-09-21
dc.date2008-01-16
dc.date.accessioned2026-07-07T13:07:26Z
dc.date.available2026-07-07T13:07:26Z
dc.descriptionThis paper studies non-crossing geometric perfect matchings. Two such perfect matchings are \emph{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\in\Oh{\log n}$, there is a sequence of perfect matchings $M=M_0,M_1,...,M_k=M'$, such that each $M_i$ is compatible with $M_{i+1}$. This improves the previous best bound of $k\leq n-2$. We then study the conjecture: \emph{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.
dc.descriptionimproved exposition and improved results
dc.identifierhttps://arxiv.org/abs/0709.3375
dc.identifierhttp://arxiv.org/abs/0709.3375
dc.identifierComputational Geometry: Theory & Applications 42(6-7):617-626, 2009.
dc.identifierdoi:10.1016/j.comgeo.2008.12.005
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/228091
dc.subjectCombinatorics
dc.subject52C99
dc.titleCompatible Geometric Matchings
dc.typetext

Files

Collections

arXiv