Cutting Dense Point Sets in Half

Herbert Edelsbrunner
Department of Computer Science
University of Illinois at Urbana-Champaign

Pavel Valtr
Institut für Informatik
Freie Universität Berlin

Emo Welzl
Institut für Informatik
Freie Universität Berlin

Report B 94-06 March 1994

Get the report here or by anonymous ftp: 
File:   pub/reports/
A halving hyperplane of a set S of n points in $R^d$ contains d affinely independent points of S so that equally many of the points off the hyperplane lie in each of the two half-spaces. We prove bounds on the number of halving hyperplanes under the condition that the ratio of largest over smallest distance between any two points is at most $\delta n^1/d$, $\delta$ some constant. Such a set S is called dense.
In d = 2 dimensions, the number of halving lines for a dense set can be as much as $\omega(n log n)$, and it cannot exceed $0(n^5/4 / log*n)$. The upper bound improves over the current best bound of $0(n^3/2 / log*n)$ which holds more generally without any density assumption. In d = 3 dimensions we show that $0(n^7/3)$ is an upper bound on the number of halving planes for a dense set. The proof is based on a metric argument that can be extended to $d \geq 4$ dimensions, where it leads to $0(n^{d-\frac{2}{d}}$ as an upper bound for the number of halving hyperplanes.