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ᵈ and E P d+1 is a collection of n d+1 d-dimensional simplices with vertices in P, for 00. 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\'ar\'any, F\"uredi and Kleitman. As a result, any n-point set in general position in Rᵈ admits only O (n^d-1{d (d-1) ⁴+d (d-1) +}) halving hyperplanes, for any >0, which is a significant improvement over the previously best known bound O (n^d-1{ (2d) ^{d}}) in all dimensions d 5. An essential ingredient of our proof is the following semi-algebraic Tur\'an-type result of independent interest: Let (V₁, , Vₖ, E) be a hypergraph of bounded semi-algebraic description complexity in Rᵈ that satisfies |E| |V₁| |Vₖ| for some >0. Then there exist subsets Wᵢ Vᵢ that satisfy W₁ W₂ Wₖ E, and |W₁||Wₖ|= (^d (k-1) +1|V₁| |V₂||Vₖ|).