Papers for

graph drawing tool creators

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Point sets guaranteed to contain large crossing families of lines

Larger Crossing Families

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.

Wed 28 OctComputational Geometry

The gist

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.

Open → 2610.38658v1