A generalization of crossing families

Patrick SchniderarXiv 2017 · OpenReview

Abstract

For a set of points in the plane, a crossing family is a set of line segments, each joining two of the points, such that any two line segments cross. We investigate the following generalization of crossing families: a spoke set is a set of lines drawn through a point set such that each unbounded region of the induced line arrangement contains at least one point of the point set. We show that every point set has a spoke set of size $\sqrt{\frac{n}{8}}$. We also characterize the matchings obtained by selecting exactly one point in each unbounded region and connecting every such point to the point in the antipodal unbounded region.

Introduction

In discrete geometry, the study of crossing families has been a central problem for decades. A crossing family is a collection of line segments where every pair of segments intersects. A long-standing conjecture suggests that any set of $n$ points in general position should contain a crossing family of size proportional to $n$ (linear size). However, proving this has remained elusive, with the best-known lower bounds stuck at approximately $\sqrt{n/12}$.

This paper introduces spoke sets, a more flexible generalization of crossing families. By relaxing the rigid intersection requirements of crossing families into a condition on the unbounded regions of a line arrangement, the author provides new tools to tackle problems in combinatorial geometry, such as decomposing complete graphs into crossing-free spanning trees.

Defining Spoke Sets

A spoke set is defined as a collection of lines passing through a point set such that every unbounded region created by the arrangement of these lines contains at least one point from the original set. This structure is inherently related to crossing families: every crossing family induces a spoke set, but the converse is not necessarily true. Spoke matchings can even be crossing-free, offering a broader geometric framework for analysis.

Figure 1: A point set and an associated spoke set of five lines. Each unbounded region of the arrangement contains at least one point.

The Dual Perspective and Methodology

The core of the paper's methodology lies in point-line duality. This standard geometric transformation maps points to lines and lines to points, allowing complex primal problems to be solved in a dual arrangement. In the dual plane, the requirement for points to occupy specific unbounded regions translates into finding a specific type of path—a "spoke path"—through a line arrangement.

To prove the existence of these paths, the author utilizes wiring diagrams, which are topological simplifications of line arrangements. By performing specific "moves" (such as single and split crossings) on these diagrams, the author demonstrates that certain paths must exist regardless of the point set's configuration. This approach is further supported by techniques like Ham-sandwich cuts to partition point sets and the use of mutually avoiding sets to ensure geometric constraints are met.

Figure 5: The relationship between the primal plane (left) and the dual wiring diagram (right). Duality allows the search for spoke sets to be framed as a path-finding problem in a structured arrangement.

Key Results

The paper achieves two primary breakthroughs:

  1. Improved Lower Bound: It is proven that every set of $n$ points in general position contains a spoke set of size at least $\sqrt{n/8}$. This quantitatively improves upon the $\sqrt{n/12}$ bound typically associated with traditional crossing families.
  2. Geometric Characterization: The paper provides a complete characterization of "spoke matchings." A matching is a spoke matching if and only if no two edges are parallel, stabbing vertices lie within the convex hulls of the edges they stab, and stabbing chains follow specific nesting rules.

Conclusion and Future Work

While the improvement to $\sqrt{n/8}$ is significant, the "Linear Size Conjecture" remains the ultimate goal. The author notes that while some point sets lack large mutually avoiding subsets, it remains possible that large spoke sets exist via alternative constructions. Future research may focus on bridging the gap between spoke sets and crossing families to determine if the flexibility of the former can finally unlock a linear bound for the latter.

Summary updated

Abstract

For a set of points in the plane, a \emph{crossing family} is a set of line segments, each joining two of the points, such that any two line segments cross. We investigate the following generalization of crossing families: a \emph{spoke set} is a set of lines drawn through a point set such that each unbounded region of the induced line arrangement contains at least one point of the point set. We show that every point set has a spoke set of size $\sqrt{\frac{n}{8}}$. We also characterize the matchings obtained by selecting exactly one point in each unbounded region and connecting every such point to the point in the antipodal unbounded region.
BibTeX
@misc{schnider2017generalization,
  author = {Patrick Schnider},
  title = {{A generalization of crossing families}},
  year = {2017},
  eprint = {1702.07555},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1702.07555},
}
Figure