2016/12/11 by Leonardo Martínez-Sandoval, Martínez-Sandoval, Leonardo, Roee Tamam +1
Computer Science · Mathematics · #52A20 #52A35 #Advanced Statistical Methods and Models #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1612.03435
openalex publication_date 2016/12/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a notion of depth with respect to a finite family F of convex sets in ℝd which we call depF. We begin showing that depF satisfies some expected properties for a measure of depth and that this definition is closely related to the notion of depth proposed by J. Tukey. We show that some properties of Tukey depth extend to depF and we point out some key differences. We then focus on the following centerpoint-type question: what is the best depth αd,k that we can guarantee under the hypothesis that the family F is k-intersecting? We show a key connection between this problem and a purely combinatorial problem on hitting sets. The relationship is useful in both directions. On the one hand, for values of k close to d the combinatorial interpretation gives a good bound for k. On the other hand, for low values of k we can use the classic Rado's centerpoint theorem to get combinatorial results of independent interest. For intermediate values of k we present a probabilistic framework to improve the bounds and illustrate its use in the case k≈ d/2. These results can be though of as an interpolation between Helly's theorem and Rado's centerpoint theorem. As an application of these results we find a Helly-type theorem for fractional hyperplane transversals. We also give an alternative and simpler proof for a transversal result of A. Holmsen.