TL;DR
While mathematicians have long studied "plane" (crossing-free) perfect matchings, this paper explores what happens when we intentionally allow exactly $k$ crossings. The authors establish the range of $k$ for which a matching is guaranteed to exist, prove that some point sets have strange "gaps" in their crossing counts, and show that convex point sets are often the extremal cases for these counts.
What Problem Does This Paper Address?
In discrete geometry, a classic result states that any set of $n$ points in the plane admits at least $C_{n/2}$ (the $(n/2)$-th Catalan number) perfect matchings that have zero crossings. These "plane matchings" are well-behaved and extensively studied.
However, as soon as you allow edges to cross, the complexity explodes. On $n$ vertices, there are $(n-1)!!$ possible perfect matchings—a number that grows much faster than the Catalan numbers. This paper asks: If I pick a specific number $k$, can I always find a perfect matching with exactly $k$ crossings? Furthermore, how many such matchings exist, and which point configurations give us the most (or fewest) of them?
Methods
The authors employ a mix of probabilistic proofs, constructive geometry, and exhaustive computational search:
- Probabilistic Method: To show that any point set has matchings with many crossings, they analyze a random perfect matching and use the known lower bounds for the rectilinear crossing number (the minimum number of crossings in a complete graph $K_n$).
- Constructive Geometry: They introduce the "windmill" configuration—a rotational symmetric set of three "wings"—to prove upper bounds on the maximum possible crossings a point set can support.
- Injective Mapping: To prove that convex point sets minimize matchings with $\le 2$ crossings, they develop a recursive mapping technique that transforms a matching on a convex set into one on a general set without increasing the crossing count.
- Computational Search: For small cases ($n = 6, 8, 10$), the authors used the Order Type Database, a known dataset of all combinatorially distinct point configurations, to verify their conjectures and find counter-examples.
Datasets
The paper primarily uses the Order Type Database for $n \le 10$. This is a standard benchmark in computational geometry that contains every possible "shape" a set of $n$ points can take. This allowed the authors to observe that while convex sets minimize matchings for $k=0, 1, 2$, a specific "wheel" configuration actually yields more matchings than a convex set when $k=6$ and $n=10$.
Key Insights and Ideas
- The Existence Threshold: For any "sufficiently large" $n$, you are guaranteed to find a matching with exactly $k$ crossings, provided $k$ is relatively small (roughly up to $n^2/64$).
- The "Windmill" Limit: You might think that by placing points randomly, you could get an arbitrarily high number of crossings. However, the "windmill" construction shows there's a hard ceiling: some point sets can never have more than $\approx \frac{5}{72}n^2$ crossings in any perfect matching.
- The Gap Phenomenon: Perhaps the most surprising finding is that crossing counts aren't always continuous. The authors found a set of 30 points that has a matching with 105 crossings, but no matching with 104 or 103 crossings. They proved that these "gaps" can be made arbitrarily large as $n$ increases.
- Convexity as an Extremum: Convex point sets (points on a circle) are the "simplest" configurations. The paper proves they are extremal in two ways: they minimize the number of matchings with very few crossings ($k \le 2$) and maximize the number of matchings with the absolute maximum possible crossings.
Key Results
- Existence: Any set of $n$ points admits a perfect matching with exactly $k$ crossings for $0 \le k \le \frac{1}{64}n^2 - O(n\sqrt{n})$.
- Superexponential Growth: If the number of allowed crossings $k$ grows faster than $n$ (superlinear), the number of available matchings grows superexponentially ($2^{\Omega(n \log(k/n))}$).
- Convex Minimization: For $k \in \{0, 1, 2\}$, the number of matchings with at most $k$ crossings is minimized when the points are in convex position.
- Maximal Crossings: Convex sets maximize the number of matchings with $\mu$ and $\mu-1$ crossings, where $\mu = \binom{n/2}{2}$ is the maximum possible crossings for a convex set.
Limitations and Future Work
The authors acknowledge that the computational complexity of these problems remains a major hurdle. While they settled the "existence" question for small $k$, determining if a point set admits a matching with exactly $k$ crossings is likely NP-complete in the general case.
Future research directions include:
- Determining the exact complexity of the $k$-crossing decision problem.
- Investigating if convex sets minimize the number of matchings with exactly one crossing (Open Problem 2).
- Finding the exact value of $k$ where the "wheel" configuration starts producing more matchings than the convex configuration.
Summary updated