Stabbing simplices by points and flats

الأصل · EN

The following result was proved by Barany in 1982: For every d >= 1 there exists cd > 0 such that for every n-point set S in Rᵈ there is a point p in Rᵈ contained in at least cd nᵈ⁺¹ - O(nᵈ) of the simplices spanned by S. We investigate the largest possible value of cd. It was known that cd <= 1/(2ᵈ(d+1)!) (this estimate actually holds for every point set S). We construct sets showing that cd <= (d+1)⁻⁽ᵈ⁺¹⁾, and we conjecture this estimate to be tight. The best known lower bound, due to Wagner, is cd >= gammad:= (d²+1)/((d+1)!(d+1)ᵈ⁺¹); in his method, p can be chosen as any centerpoint of S. We construct n-point sets with a centerpoint that is contained in no more than gammad nᵈ⁺¹+O(nᵈ) simplices spanned by S, thus showing that the approach using an arbitrary centerpoint cannot be further improved. We also prove that for every n-point set S in Rᵈ there exists a (d-2)-flat that stabs at least cd,d₋₂ n³ - O(n²) of the triangles spanned by S, with cd,d₋₂>=(1/24)(1- 1/(2d-1)²). To this end, we establish an equipartition result of independent interest (generalizing planar results of Buck and Buck and of Ceder): Every mass distribution in Rᵈ can be divided into 4d-2 equal parts by 2d-1 hyperplanes intersecting in a common (d-2)-flat.