##
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:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-94-06.ps.gz

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.