Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Cutting dense point sets in half
| |
|
Cutting dense point sets in half
H. Edelsbrunner1  , P. Valtr2, 3 and E. Welzl4
| (1) |
Department of Computer Science, University of Illinois at Urbana-Champaign, 61801 Urbana, IL, USA |
| (2) |
Graduiertenkolleg “Algorithmische Diskrete Mathematik,”, Freie Universität Berlin, 14195 Berlin, Germany |
| (3) |
Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic |
| (4) |
Institut Informatik, Freie Universität Berlin, 14195 Berlin, Germany |
Received: 22 March 1995 Revised: 15 January 1996
Abstract A halving hyperplane of a set S of n points in ℝ 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
δn(1/d), δ 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 Ω (n log n), and it cannot exceed O (n5/4/log*
n). The upper bound improves over the current best bound of O(n3/2/log*
n) which holds more generally without any density assumption. In d = 3 dimensions we show that O(n7/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 ≥ 4 dimensions, where it leads to O(n
d-2/d
) as an upper bound for the number of halving hyperplanes.
The research by H. Edelsbrunner was partially supported by the National Science Foundation, under Grant ASC-9200301 and the
Alan T. Waterman award, Grant CCR-9118874. The research by P. Valtr was supported by the Deutsche Forschungsgemeinschaft,
under Grant We 1265/2-1, by the Czech Republic Grant GAČR 201/94/2167, and by the Charles University Grants Nos. 351 and 361.
Part of the research by P. Valtr and E. Welzl has been carried out during a visit to the Tel Aviv University supported by
the German-Israeli Foundation for Scientific Research and Development.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|