Halving point sets (Q1126842)

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 \textit{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.