TOPICS
Search

Crossing Family


A crossing family in a finite planar point set P in general position, with no three collinear points, is a collection of line segments with endpoints in P whose every pair intersects away from the endpoints of both segments. Shared endpoints do not count as crossings (Aronov et al. 1994).

Orthaber and Schnider (2026) proved that every such n-point set contains a crossing family of size at least

 (4-sqrt(10))/3|_n/22_|,

where |_x_| is the floor function. This gives an explicit universal linear lower bound, with asymptotic coefficient (4-sqrt(10))/66. The geometric notion differs from crossing families of sets in combinatorial optimization.

Let f(P) be the largest crossing-family size and C(P) the number of crossings in the complete straight-line drawing on P. Orthaber and Schnider (2026) also proved, for n>=4,

 f(P)>=n/2-nsqrt(1-(C(P))/((n; 4))).

The count C(P) belongs to the fixed drawing, rather than being the minimum over all drawings in the rectilinear crossing number.


See also

General Position, Line Segment

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Aronov, B.; Erdős, P.; Goddard, W.; Kleitman, D. J.; Klugerman, M.; Pach, J.; and Schulman, L. J. "Crossing Families." Combinatorica 14, 127-134, 1994. https://doi.org/10.1007/BF01215345.Orthaber, J. and Schnider, P. "Larger Crossing Families." 28 Oct 2026. https://arxiv.org/abs/2610.38658.

Cite this as:

Weisstein, Eric W. "Crossing Family." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CrossingFamily.html

Subject classifications