Larger Crossing Families

arXiv:2610.38658 · math.CO, cs.CG · Submitted 2026-10-28 · Read on arXiv

math.CO, cs.CG

Submitted: 2026-10-28

Updated: 2026-10-28

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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 n over…

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 n over 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.

Related papers