zbMATH — the first resource for mathematics

Halving point sets. (English) Zbl 0911.52010
Given \(n\) points in \(\mathbb R^d\), a hyperplane is called halving if it has at most \(\lfloor n/2 \rfloor\) points on either side.
This paper surveys known results about the question: How many partitions of a point set (into the points on one side, on the hyperplane, and on the other side) by halving hyperplanes can be realized by an \(n\)-point set in \(R^d\)? This is a special case of the famous \(k\)-set problem. For the planar case the authors discuss the recent upper bound due to T. Dey [Discrete Comput. Geom. 19, No. 3, 373-382 (1998; Zbl 0899.68107)] and described the Lovász crossing lemma, a useful result in this topic. The remainder of the paper states the known bounds on the number of \(j\)-facets and presents connections to other topics in discrete geometry and algorithms. These include the upper bound theorem, \(k\)-levels and parametric matroid optimization.

52C10 Erdős problems and related topics of discrete geometry
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
52B55 Computational aspects related to convexity
68R05 Combinatorics in computer science
68Q25 Analysis of algorithms and problem complexity
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: EMIS EuDML