An improvement on the Rado bound for the centerline depth

Abstract

Let $\mu$ be a Borel probability measure in ${\mathbb{R}}^d$. For a $k$-flat $\alpha$ consider the value $\inf \mu (H)$, where $H$ runs through all half-spaces containing $\alpha$. This infimum is called the half-space depth of $\alpha$. Bukh, Matoušek and Nivasch conjectured that for every $\mu$ and every $0\le k<d$ there exists a $k$-flat with the depth at least $\frac{k+1}{k+d+1}$. The Rado Centerpoint Theorem implies a lower bound of $\frac{1}{d+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\ge 3$ we show that there is a 1-dimensional line with the depth at least $\frac{1}{d}+\frac{1}{3d^3}$. As a corollary, for all $(d,k)$ satisfying $0<k<d-1$ there exists a $k$-flat with depth at least $\frac{1}{d+1-k}+\frac{1}{3(d+1-k{)}^3}$.

Version v.2 is the one accepted to Discrete & Computational Geometry. As suggested by the referees, we changed the title and the order of exposition