# Cutting dense point sets in half

Edelsbrunner H, Valtr P, Welzl E. 1997. Cutting dense point sets in half. Discrete & Computational Geometry. 17(3), 243–255.

Download

**No fulltext has been uploaded. References only!**

*Journal Article*|

*Published*

Author

Edelsbrunner, Herbert

^{IST Austria}^{}; Valtr, Pavel; Welzl, EmoAbstract

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 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(d-2/d)) as an upper bound for the number of halving hyperplanes.

Publishing Year

Date Published

1997-04-01

Journal Title

Discrete & Computational Geometry

Acknowledgement

Partially supported by the National Science Foundation, under Grant ASC-9200301 and the Alan T. Waterman award, Grant CCR-9118874.

Volume

17

Issue

3

Page

243 - 255

IST-REx-ID

### Cite this

Edelsbrunner H, Valtr P, Welzl E. Cutting dense point sets in half.

*Discrete & Computational Geometry*. 1997;17(3):243-255. doi:10.1007/PL00009291Edelsbrunner, H., Valtr, P., & Welzl, E. (1997). Cutting dense point sets in half.

*Discrete & Computational Geometry*. Springer. https://doi.org/10.1007/PL00009291Edelsbrunner, Herbert, Pavel Valtr, and Emo Welzl. “Cutting Dense Point Sets in Half.”

*Discrete & Computational Geometry*. Springer, 1997. https://doi.org/10.1007/PL00009291.H. Edelsbrunner, P. Valtr, and E. Welzl, “Cutting dense point sets in half,”

*Discrete & Computational Geometry*, vol. 17, no. 3. Springer, pp. 243–255, 1997.Edelsbrunner, Herbert, et al. “Cutting Dense Point Sets in Half.”

*Discrete & Computational Geometry*, vol. 17, no. 3, Springer, 1997, pp. 243–55, doi:10.1007/PL00009291.