2016/03/03 by Alexander Magazinov, Magazinov, Alexander, Attila Pór +1
Computer Science · Engineering · Mathematics · #52A30 #52C35 #68U05 #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG) #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.1603.01641
openalex publication_date 2016/03/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let μ be a Borel probability measure in \mathbb Rd. For a k-flat α consider the value inf μ(H), where H runs through all half-spaces containing α. This infimum is called the half-space depth of α. Bukh, Matoušek and Nivasch conjectured that for every μ and every 0 ≤ k < d there exists a k-flat with the depth at least \tfrack + 1k + d + 1. The Rado Centerpoint Theorem implies a lower bound of \tfrac1d + 1 - k (the Rado bound), which is, in general, much weaker. Whenever the Rado bound coincides with the bound conjectured by Bukh, Matoušek and Nivasch, i.e., for k = 0 and k = d - 1, it is known to be optimal. In this paper we show that for all other pairs (d, k) one can improve on the Rado bound. If k = 1 and d ≥ 3 we show that there is a 1-dimensional line with the depth at least \tfrac1d + \tfrac13d3. As a corollary, for all (d, k) satisfying 0 < k < d - 1 there exists a k-flat with depth at least \tfrac1d + 1 - k + \tfrac13(d + 1 - k)3.