Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the 15th International Conference and Workshops on Algorithms and Computation, WALCOM 2021
DOI: 10.7155/jgaa.00591
On Compatible Matchings
Oswin Aichholzer,
Alan Arroyo,
Zuzana Masárová,
Irene Parada,
Daniel Perz,
Alexander Pilz,
Josef Tkadlec, and
Birgit Vogtenhuber
Vol. 26, no. 2, pp. 225-240, 2022. Regular paper.
Abstract A matching is compatible to two or more labeled point sets of size $n$ with labels $\{1,\dots,n\}$ if its straight-line drawing on each of these point sets is crossing-free.
We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane.
We show that for any two labeled sets of $n$ points in convex position there exists a compatible matching with $\lfloor \sqrt {2n+1} -1\rfloor$ edges.
More generally, for any $\ell$ labeled point sets we construct compatible matchings of size $\Omega(n^{1/\ell})$.
As a corresponding upper bound, we use probabilistic arguments to show that for any $\ell$ given sets of $n$ points there exists a labeling of each set such that the largest compatible matching has $O(n^{2/(\ell+1)})$ edges.
Finally, we show that $\Theta(\log n)$ copies of any set of $n$ points are necessary and sufficient for the existence of labelings of these point sets such that any compatible matching consists only of a single edge.
This work is licensed under the terms of the CC-BY license.
|
Submitted: April 2021.
Reviewed: August 2021.
Revised: October 2021.
Accepted: December 2021.
Final: January 2022.
Published: June 2022.
|
Journal Supporters
|