Author(s):

Edelsbrunner, Herbert; Valtr, Pavel; Welzl, Emo

Article Title: 
Cutting dense point sets in half

Affiliation 

Abstract: 
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 halfspaces. 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 O (n(5/4)/log* n). The upper bound improves over the current best bound of O (n(3/2)/log* n) which holds more generally without any density assumption. In d = 3 dimensions we show that O (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 greater than or equal to 4 dimensions, where it leads to O (n(d2/d)) as an upper bound for the number of halving hyperplanes.

Journal Title:

Discrete & Computational Geometry

Volume: 
17

Issue 
3

ISSN:

01795376

Publisher:

Springer

Date Published:

19970401

Start Page: 
243

End Page:

255

Sponsor: 
Partially supported by the National Science Foundation, under Grant ASC9200301 and the Alan T. Waterman award, Grant CCR9118874.

DOI: 
10.1007/PL00009291

Open access: 
no 