Title: Halving Point Sets

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. 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 $\mathbb{R}^d$?

1991 Mathematics Subject Classification: 52C10, 52B05, 52B55, 68R05, 68Q25, 68U05

Keywords and Phrases: combinatorial geometry, computational geometry, $k$-sets, $k$-levels, probabilistic method, matroid optimization, oriented matroids, Upper Bound Theorem.

Full text: dvi.gz 16 k, dvi 34 k, ps.gz 65 k.

Home Page of DOCUMENTA MATHEMATICA