Mathematics – Combinatorics
Scientific paper
2007-09-21
Computational Geometry: Theory & Applications 42(6-7):617-626, 2009.
Mathematics
Combinatorics
improved exposition and improved results
Scientific paper
10.1016/j.comgeo.2008.12.005
This 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.
Aichholzer Oswin
Bereg Sergey
Dumitrescu Adrian
García Alfredo
Huemer Clemens
No associations
LandOfFree
Compatible Geometric Matchings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Compatible Geometric Matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compatible Geometric Matchings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-256515