Perfect Matchings with Crossings

O. Aichholzer, R. Fabila-Monroy, P. Kindermann, I. Parada, R. Paul, D. Perz, P. Schnider, and B. Vogtenhuber

Abstract:

In this paper, we analyze the number of straight-line perfect matchings with $k$ crossings on point sets of size $n$ = $2m$ in general position. We show that for every $k\leq 5n/8-\Theta(1)$, every $n$-point set admits a perfect matching with exactly $k$ crossings and that there exist $n$-point sets where every perfect matching has fewer than $5n^2/72$ crossings. We also study the number of perfect matchings with at most $k$ crossings. Finally we show that convex point sets matchings with $n/2 \choose 2$ crossings and ${n/2 \choose 2}\!-\!1$ crossings.

Reference: O. Aichholzer, R. Fabila-Monroy, P. Kindermann, I. Parada, R. Paul, D. Perz, P. Schnider, and B. Vogtenhuber. Perfect matchings with crossings. In Proceedings of the Computational Geometry: Young Researchers Forum, pages 24-27, 2021.