Electronic Resource
Springer
Discrete & computational geometry
17 (1997), S. 243-255
ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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 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}$ , δ 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≥ 4 dimensions, where it leads to $O(n^{d-{2}/{d}})$ as an upper bound for the number of halving hyperplanes.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009291
| Library |
Location |
Call Number |
Volume/Issue/Year |
Availability |
