Caratheodory's Theorem in Depth

Abstract

Let $X$ be a finite set of points in ${\mathbb{R}}^d$. The Tukey depth of a point $q$ with respect to $X$ is the minimum number ${\tau }_X(q)$ of points of $X$ in a halfspace containing $q$. In this paper we prove a depth version of Carathéodory's theorem. In particular, we prove that there exists a constant $c$ (that depends only on $d$ and ${\tau }_X(q)$) and pairwise disjoint sets $X_1,\dots ,X_{d+1}\subset X$ such that the following holds. Each $X_i$ has at least $c|X|$ points, and for every choice of points $x_i$ in $X_i$, $q$ is a convex combination of $x_1,\dots ,x_{d+1}$. We also prove depth versions of Helly's and Kirchberger's theorems.