Cutting dense point sets in half
Herbert Edelsbrunner, Pável Valtr, Emo Welzl · 1994
A halving hyperplane of a set S of n points in Rd 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 δn1/d, δ some constant. Such a set S is called dense.