Caratheodory's Theorem in Depth

2015/09/15 by Fabila-Monroy, Ruy, Huemer, Clemens
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1509.04575

Abstract

Let X be a finite set of points in ℝ^d. The Tukey depth of a point q with respect to X is the minimum number τ_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 τ_X(q)) and pairwise disjoint sets X₁,…, X_d+1 ⊂ 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₁,…, x_d+1. We also prove depth versions of Helly's and Kirchberger's theorems.

Related

• Depth with respect to a family of convex sets
• Enclosing Depth and other Depth Measures
• Tukey Depth Histograms
• Depth of segments and circles through points enclosing many points: a note
• Theorems of Carathéodory, Helly, and Tverberg without dimension