Improved Bounds for Point Selections and Halving Hyperplanes in Higher Dimensions
Natan Rubin · Society for Industrial and Applied Mathematics eBooks · 2024
Let (P, E) be a (d + 1)-uniform geometric hypergraph, where P is an n-point set in general position in ℝd and is a collection of d-dimensional simplices with vertices in P, for 0 0. This is a dramatic improvement in all dimensions d ≥ 3, over the previous lower bounds of the general form ɛ(cd)d+1nd+1, which date back to the seminal 1991 work of Alon, Bárány, Füredi and Kleitman.