Linear-size crossing families in planar point sets (the crossing family problem)

A crossing family in a set $P$ of $n$ points in general position in the plane is a collection of straight-line segments spanned by $P$ that pairwise cross in their interiors. Aronov, Erdős, Goddard, Kleitman, Klugerman, Pach, and Schulman (SoCG 1991; Combinatorica 1994) proved that every such $P$ contains a crossing family of size at least $\sqrt{n/12}$ and conjectured that a linear-size family always exists. The conjecture, recorded in the Brass–Moser–Pach problem collection, remains open: after the 2019/2021 breakthrough of Pach, Rubin, and Tardos guaranteeing $n/2^{O(\sqrt{\log n})}=n^{1-o(1)}$ pairwise crossing segments in every $n$-point set, and explicit constructions capping any guarantee at $8\lceil n/41\rceil\approx0.195n$, the central question — whether some constant $c>0$ forces a crossing family of size at least $cn$ in every $n$-point set in general position, i.e. whether the extremal function $T(n)$ satisfies $T(n)=\Theta(n)$ — is unresolved.

Background

Two straight-line segments in the plane cross if they share exactly one point and that point lies in the interior of both. A finite point set is in general position if no three of its points are collinear. For a set $P$ of $n$ points in general position in the plane, a crossing family is a collection of segments, each joining two points of $P$, such that every two of the segments cross; since crossing segments cannot share endpoints, a crossing family of size $k$ is a matching of $k$ pairwise crossing edges of the complete straight-line graph on $P$ (called a complete geometric graph). Crossing families were introduced by Aronov, Erdős, Goddard, Kleitman, Klugerman, Pach, and Schulman (SoCG 1991; journal version Combinatorica 1994), who asked how large a crossing family must appear in every point set. Writing $T(n)$ (also denoted $\mathrm{cf}(n)$ or $\mathrm{crf}(n)$ in the literature) for the minimum, over all $n$-point sets in general position, of the size of a largest crossing family, they proved $T(n)\ge\sqrt{n/12}$. Their key notion: two point sets $A$ and $B$ are mutually avoiding if no line through two points of one set intersects the convex hull of the other; two mutually avoiding $k$-point sets can be bijectively paired into $k$ pairwise crossing segments, and an argument based on the Erdős–Szekeres monotone-subsequence theorem (every sequence of $N$ distinct numbers contains a monotone subsequence of length at least $\lceil\sqrt{N}\rceil$) produces mutually avoiding subsets of size $\sqrt{n/12}$. They also constructed point sets in which every crossing family is small: a 4-point configuration in non-convex position (one point inside the triangle formed by the other three, so that no two segments spanned by the set cross) whose twin-replacement blow-up (replacing each point by a very close pair of 'twins', which preserves the ratio of points usable by a crossing family) yields arbitrarily large point sets whose maximum crossing family uses only half of the points, i.e. has at most $n/4$ segments. Because a crossing family is a matching, $T(n)\le\lfloor n/2\rfloor$ holds trivially, and convex position (points that are the vertices of a convex polygon) attains $\lfloor n/2\rfloor$ via pairwise crossing 'diagonals', so the extremal behavior is governed by non-convex configurations. The authors conjectured that a linear-size family always exists, i.e. $T(n)=\Theta(n)$; the conjecture is recorded in the Brass–Moser–Pach problem collection Research Problems in Discrete Geometry (2005) and has become a standard open problem of combinatorial geometry. Subsequent evidence: Valtr (Combinatorica 1996) showed that $n$ points chosen independently at random in a convex region contain a linear-size crossing family with high probability and that dense point sets (in which the ratio of the largest to the smallest pairwise distance is $O(\sqrt{n})$) admit almost-linear-size families; he also constructed dense point sets with no mutually avoiding pair larger than $O(\sqrt{n})$, proving the original proof technique is asymptotically tight and cannot yield linearity. A breakthrough by Pach, Rubin, and Tardos (STOC 2019; Advances in Mathematics 2021) gave the first improvement in 25 years: every $n$-point set determines at least $n/2^{O(\sqrt{\log n})}=n^{1-o(1)}$ pairwise crossing segments, constructively, with an extension to geometric graphs with $n^{2-o(1)}$ edges. On the other side, explicit constructions cap the guarantee: Evans and Saeedi (2019) built point sets with no crossing family larger than $5\lceil n/24\rceil$, improved by Aichholzer, Kynčl, Scheucher, Vogtenhuber, and Valtr (2022) to $8\lceil n/41\rceil\approx0.195n$ via a 41-point set with no 9-crossing family; the same authors combined exhaustive enumeration of order types (the combinatorial record of a point set given by the orientation of every point triple, which can be exhaustively classified for small $n$) with SAT solvers (complete decision procedures for propositional satisfiability) to show that every 15-point set contains a crossing family of size 4. The question is closely tied to the Turán-type edge-bound theory of quasi-planar geometric graphs (a geometric graph is $t$-quasi-planar if it contains no $t$ pairwise crossing edges; the conjectured tight bound of about $t^{1+o_t(1)}n$ edges is in spirit a generalization of the crossing family question), to packing edge-disjoint plane spanning trees into complete geometric graphs (a crossing family of size $k$ yields $\Omega(k)$ such trees), and to lower bounds on the number of triangulations of a point set. Natural relaxations behave differently and isolate the difficulty: matchings whose segments form a connected union are always linear (Aichholzer, Cabello, Mészáros, Schnider, Soukup 2024), and crossing families of $k$-edge paths for $k\ge3$ are linear and tight (Álvarez-Rebollar et al. 2024), yet for single edges — the original problem — nothing between $n^{1-o(1)}$ and $0.195n$ is known.

Problem Statement

Determine the asymptotic order of $T(n):=\min_{|P|=n}\max\{k:\;P\text{ contains a crossing family of size }k\}$, where the minimum ranges over all sets $P$ of $n$ points in the plane in general position (no three points of $P$ are collinear), and a crossing family is a collection of segments, each joining two points of $P$, such that every two of the segments cross, i.e. share exactly one point and that point lies in the interior of both segments. In particular: does there exist a constant $c>0$ such that every set of $n$ points in general position in the plane contains a crossing family of size at least $cn$ — equivalently, is $T(n)=\Theta(n)$? The current state of knowledge is $n/2^{O(\sqrt{\log n})}\le T(n)\le 8\lceil n/41\rceil$ (lower bound: Pach–Rubin–Tardos 2021; upper bound: Aichholzer–Kynčl–Scheucher–Vogtenhuber–Valtr 2022). The question is resolved either by establishing a linear lower bound with an explicit or existential constant $c$ valid for all point sets in general position, or by constructing, for infinitely many $n$, realizable point sets in general position whose largest crossing family has sublinear size $o(n)$ (or $\Theta(g(n))$ for an explicit sublinear $g$) together with a proof that no larger crossing family exists in those sets. Historical context: when the problem was posed, the possibilities linear / $n^{\alpha}$ with $1/2<\alpha<1$ / $\Theta(\sqrt{n})$ were all open; the $n^{1-o(1)}$ lower bound of Pach–Rubin–Tardos has since refuted every sublinear-polynomial and $\Theta(\sqrt{n})$ scenario, so the surviving question is exactly linear versus sublinear.

References

1. B. Aronov, P. Erdős, W. Goddard, D. J. Kleitman, M. Klugerman, J. Pach, L. J. Schulman, Crossing families, Proceedings of the Seventh Annual ACM Symposium on Computational Geometry (SoCG '91), ACM, 1991, pp. 351–356, DOI 10.1145/109648.109687, https://doi.org/10.1145/109648.109687 (source of the open question)
2. B. Aronov, P. Erdős, W. Goddard, D. J. Kleitman, M. Klugerman, J. Pach, L. J. Schulman, Crossing families, Combinatorica 14(2):127–134, 1994, DOI 10.1007/BF01215345, https://doi.org/10.1007/BF01215345 (journal version)
3. J. Pach, N. Rubin, G. Tardos, Planar point sets determine many pairwise crossing segments, Advances in Mathematics 386:107779, 2021, DOI 10.1016/j.aim.2021.107779, https://doi.org/10.1016/j.aim.2021.107779 (author preprint arXiv:1904.08845, https://arxiv.org/abs/1904.08845)
4. W. Evans, N. Saeedi, On problems related to crossing families, arXiv:1906.00191, 2019, https://arxiv.org/abs/1906.00191
5. O. Aichholzer, J. Kynčl, M. Scheucher, B. Vogtenhuber, P. Valtr, On crossing-families in planar point sets, Computational Geometry 107:101899, 2022, DOI 10.1016/j.comgeo.2022.101899, https://doi.org/10.1016/j.comgeo.2022.101899 (author preprint arXiv:2109.10705, https://arxiv.org/abs/2109.10705)
6. T. Antić, M. Balko, B. Vogtenhuber, Crossing and non-crossing families, arXiv:2508.17277, 2025, https://arxiv.org/abs/2508.17277
7. J. L. Álvarez-Rebollar, J. Cravioto-Lagos, N. Marín, O. Solé-Pi, J. Urrutia, Crossing and intersecting families of geometric graphs on point sets, Graphs and Combinatorics 40(1), 2024, DOI 10.1007/s00373-023-02734-9, https://doi.org/10.1007/s00373-023-02734-9 (author preprint arXiv:2211.09904, https://arxiv.org/abs/2211.09904)
8. P. Valtr, Lines, line-point incidences and crossing families in dense sets, Combinatorica 16(2):269–294, 1996, DOI 10.1007/BF01844852, https://doi.org/10.1007/BF01844852
9. P. Brass, W. Moser, J. Pach, Research Problems in Discrete Geometry, Springer, New York, 2005, DOI 10.1007/0-387-29929-7, https://doi.org/10.1007/0-387-29929-7 (standard record of the $T(n)=\Theta(n)$ conjecture; see also Pach–Rubin–Tardos 2021 and Antić–Balko–Vogtenhuber 2025)
10. O. Aichholzer, S. Cabello, V. Mészáros, P. Schnider, J. Soukup, Connected Matchings, arXiv:2407.06131, 2024, https://arxiv.org/abs/2407.06131
11. R. Fulek, A. Suk, On disjoint crossing families in geometric graphs, arXiv:1004.2850, 2010, https://arxiv.org/abs/1004.2850 (journal version in Thirty Essays on Geometric Graph Theory, Springer, 2013, DOI 10.1007/978-1-4614-0110-0_15)
12. P. Schnider, A generalization of crossing families, arXiv:1702.07555, 2017, https://arxiv.org/abs/1702.07555
13. A. Brötzner, R. Ganian, T. Hamm, F. Klute, I. Parada, Crossing and Independent Families Among Polygons, Proceedings of the International Symposium on Algorithms and Data Structures (WADS 2025), LIPIcs, DOI 10.4230/LIPIcs.WADS.2025.11, https://doi.org/10.4230/LIPIcs.WADS.2025.11