Point sets guaranteed to contain large crossing families of lines
Larger Crossing Families
Computational Geometry
Summary
The paper studies crossing families, groups of line segments between points that all cross each other, in sets of points on a plane. The authors found a fixed fraction of points—about 1 in 79—that always form a crossing family, showing such groups exist in surprisingly large sizes. They also explore situations where even bigger crossing families appear, like when the set avoids certain four-point shapes or has many line crossings overall. This advances understanding of the geometric ways points can be connected with crossing lines.
What this means in practice
- •For computational geometry developers: Design better geometric algorithms by using guaranteed large crossing families to optimize structures involving intersecting edges.
- •For graph drawing tool creators: Improve visualization tools by leveraging guaranteed large crossing families to ensure complex intersection patterns in graph layouts.
Authors
Joachim Orthaber, Patrick Schnider
Abstract
We give the first explicit constant for crossing families of linear size by showing that every set of $n$ points in general position in the plane contains a crossing family of size approximately $\frac{n}{79}$. We further identify some conditions where there are even larger crossing families. The first such condition forbids the existence of a large different pattern, namely non-convex 4-clusters: We show that every point set contains either a large non-convex 4-cluster or a large crossing family. The second condition is the existence of many crossings: We give a bound for the size of a crossing family in terms of the number of crossings of the complete geometric graph drawn on the point set.