The Crossing Spectrum of Geometric Matchings

23 concepts3 papers2 proposals

In computational geometry, perfect matchings on planar point sets have traditionally been studied under a strict binary condition: they are either "plane" (completely crossing-free) or they are not. We have long understood how to construct crossing-free matchings, as well as matchings that maximize the total number of intersections. However, a recent wave of research shifts focus to the largely uncharted middle ground: the exact crossing spectrum.

Instead of treating crossings as a flaw to be avoided, this line of work investigates how the spatial arrangement of points dictates our ability to engineer matchings with exactly $k$ crossings, or to find highly structured crossing and connected subgraphs.

The Intermediate Crossing Spectrum

If you are given $n$ points in a plane, can you always find a perfect matching that crosses exactly $k$ times?

Intuitively, this is difficult because crossings are highly interdependent. Swapping the endpoints of two edges to fix or introduce a crossing can cause a cascade of unexpected intersections elsewhere in the graph. In Perfect Matchings with Crossings and its journal counterpart Perfect Matchings with Crossings, Oswin Aichholzer et al. established that a perfect matching with exactly $k$ crossings is guaranteed to exist for a continuous range of $k$ from zero up to a lower bound threshold of approximately $n^2/64$.

Beyond this threshold, the spectrum becomes unpredictable. For certain point configurations, "gaps" emerge—specific integer values of $k$ for which no perfect matching exists, even though matchings with both fewer and more crossings can be constructed.

[0]-----------------[n²/64] . . . . . [Gaps / Discontinuous] . . . . . [Max Crossings]
  ▲                    ▲
  └─ Guaranteed Continuous Range ──────┘

To understand why these thresholds and gaps exist, the authors look to extremal point configurations. The most vital benchmark is convex position, where all points lie on the boundary of a circle.

Convex configurations act as a geometric anchor point:

  • Minimizing Low Crossings: Convex sets minimize the number of perfect matchings that have very few crossings ($k = 0, 1,$ or $2$). To prove this, Oswin Aichholzer et al. developed a recursive mapping technique that transforms matchings from a convex configuration to a general configuration without ever increasing the crossing count.
  • Maximizing High Crossings: Conversely, convex sets maximize the potential for high crossing counts. Because no point is "trapped" inside a hull of other points, edges can stretch across the entire configuration, maximizing intersection opportunities.

To find the absolute upper limit of the crossing spectrum for any point set, the authors introduced the windmill configuration. This geometry uses three symmetrically arranged "wings" of points. By analyzing how edges interact across these wings, the authors proved that the maximum number of crossings any perfect matching can support is strictly bounded by a hard ceiling of approximately $(5/72)n^2$.

The See-Saw of Crossing and Non-Crossing Families

A parallel way to view this problem is through the lens of mutually crossing families—sets of line segments where every pair intersects.

In Crossing and Non-Crossing Families, Todor Antic et al. exposed a structural see-saw relationship between crossing and non-crossing arrangements. The global geometric structure of a point set forces a trade-off: if you deliberately forbid certain orderly, non-crossing structures from forming, the point set is mathematically forced to yield much larger crossing families.

By framing the problem around what a point set cannot cleanly accommodate, the authors established tighter bounds on the size of crossing families that can be guaranteed in any arbitrary point distribution.

Introducing Connectivity Constraints

What happens if we demand that our matching not only avoids crossing itself, but also maintains structural unity? This is the problem of connected matchings, explored by Oswin Aichholzer et al. in Connected Matchings. Here, the goal is to find a set of non-overlapping line segments whose union forms a single, mathematically connected component.

  o-------o
          |
  o-------o
  |
  o-------o   (Segments touch only at endpoints to maintain 
               connectivity without crossing)

The tension here lies between local matching constraints and global connectivity. If points are clustered into isolated, adversarial groups, drawing an edge to connect two distant clusters risks crossing existing local edges or leaving internal points isolated.

The authors proved that an $O(n \log n)$ algorithm can always extract a connected matching containing at least $(5n+1)/27$ edges from any point set. However, they also demonstrated that this is close to the absolute physical limit: there exist worst-case point configurations that make it impossible to ever guarantee a connected matching larger than roughly $\sim n/3$ points.

Summary

Together, these papers paint a comprehensive picture of the geometric constraints governing planar point sets. Whether by mapping the exact integer spectrum of $k$-crossings, balancing crossing families against non-crossing structures, or tracing the boundaries of connected matchings, this research direction shows that crossings are not random chaos. Instead, they form a highly predictable, structurally bounded spectrum dictated entirely by the underlying geometry of the points.

Key Foundational Work

Perfect Matchings with Crossings (2022) — contributed 11 concept elements to this direction.
Perfect Matchings with Crossings (2024) — contributed 10 concept elements to this direction.
Connected Matchings (2024) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_existence_of_k_crossing_matchings_4aeba64b,
  title = {existence of k-crossing matchings},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/existence-of-k-crossing-matchings/rdr_4aeba64b17664c70abe12d5d3d2f5351},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_existence_of_k_crossing_matchings_4aeba64b_v1,
  title = {existence of k-crossing matchings},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/existence-of-k-crossing-matchings/rdr_4aeba64b17664c70abe12d5d3d2f5351/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake