Halving point sets

Artur Andrzejak, Emo WelzlEMS 1998 · DOI · OpenAlex

Abstract

Given $n$ points in $\mathbb{R}^d$, a hyperplane is called halving if it has at most $n/2$ points on either side. This paper explores the combinatorial complexity of such partitions: specifically, how many distinct ways a point set can be divided by halving hyperplanes. We survey the state-of-the-art techniques (circa 1998), highlighting the breakthrough $O(n^{4/3})$ upper bound in 2D and the application of probabilistic methods to higher-dimensional configurations.

Introduction

A fundamental question in discrete geometry asks how many ways a set of $n$ points can be split exactly in half by a hyperplane. A halving hyperplane (a line in 2D, a plane in 3D) is one that leaves approximately half the points on either side. Determining the maximum number of such partitions is a notoriously difficult combinatorial challenge.

This problem has deep implications for several computational fields:

  • Algorithmic Optimization: Finding hyperplanes that minimize the sum of Euclidean distances to a point set.
  • Range Searching: Understanding the complexity of spatial data queries.
  • Matroid Theory: Exploring the structural properties of discrete geometric configurations.

Despite its simple premise, a massive gap has historically existed between known lower bounds (what is achievable) and upper bounds (the mathematical limit).

Methodological Framework

The paper synthesizes several sophisticated mathematical "toolkits" to address the problem:

The Crossing Lemma

In 2D, halving edges—lines connecting two points that bisect the set—form a geometric graph. By utilizing the "crossing lemma" from graph theory, which relates the number of edges to the number of necessary edge crossings, researchers like Tamal Dey derived a tighter upper bound for planar sets.

Probabilistic Methods and Random Sampling

To bound the number of $j$-facets (the $d$-dimensional generalization of halving edges), the authors employ techniques popularized by Clarkson and Shor. By taking a random sample of points and applying the "Upper Bound Theorem" for convex polytopes, they can infer limits on the original set's complexity.

Duality and $k$-levels

A standard geometric technique involves mapping points to lines and lines to points. In this "dual" space, the problem of finding halving edges transforms into identifying vertices on the middle "level" of a line arrangement. This connects the problem to parametric matroid optimization.

Key Insights and Geometric Duality

The most significant insight in 2D is that the graph of halving edges cannot have an excessive number of crossings. Dey demonstrated that the number of crossings is $O(n^2)$, which, when applied to the crossing lemma, collapsed the upper bound from $O(n^{3/2})$ to $O(n^{4/3})$.

Additionally, the paper discusses a "Continuous Motion" proof technique. By starting with a simple configuration (like a regular polygon) and continuously moving points to any other configuration, researchers can show that specific geometric identities remain invariant. This provides a structural "anchor" for properties that apply to all point sets.

Key Results

  • 2D Breakthrough: The upper bound for halving edges in the plane is $O(n^{4/3})$. The best lower bound remains $\Omega(n \log n)$.
  • 3D Bounds: The number of halving triangles in 3D is bounded by $O(n^{8/3})$.
  • General Dimension ($d$): The authors provide a generalized bound for $j$-facets as $O(n^{\lfloor d/2 \rfloor} (j+1)^{\lceil d/2 \rceil})$.
  • Identity Lemma: A structural identity (Lemma 1) relates the number of crossings and point degrees in the halving graph to a fixed binomial coefficient.

Limitations and Future Work

While the $O(n^{4/3})$ result was a major step forward, a significant gap remains between the lower and upper bounds. Closing this gap is considered a "Holy Grail" of discrete geometry. Furthermore, as the dimension $d$ increases, the bounds become less tight and the proofs significantly more complex, often requiring topological theorems like the "colored" version of Tverberg’s Theorem.

Summary updated

Abstract

Given n points in R d , a hyperplane is called halving if it has at most n/2 points on either side.How many partitions of a point set (into the points on one side, on the hyperplane, and on the other side) by halving hyperplanes can be realized by an n-point set in R d ?
BibTeX
@inproceedings{andrzejak1998halving,
  author = {Artur Andrzejak and Emo Welzl},
  title = {{Halving point sets}},
  booktitle = {EMS},
  year = {1998},
  doi = {10.4171/dms/1-3/46},
}
Figure