Improved Bounds for Point Selections and Halving Hyperplanes in Higher Dimensions

Let (P, E) be a (d + 1)-uniform geometric hypergraph, where P is an n-point set in general position in R d and E ⊆ P d+1 is a collection of ϵ n d+1 d-dimensional simplices with vertices in P , for 0 < ϵ ≤ 1. We show that there is a point

simplices in E, for any fixed δ > 0. This is a dramatic improvement in all dimensions d ≥ 3, over the previous lower bounds of the general form ϵ (cd) d+1 n d+1 , which date back to the seminal 1991 work of Alon, Bárány, Füredi and Kleitman.

As a result, any n-point set in general position in R d admits only