2021/03/15 by Daniel Bertschinger, Bertschinger, Daniel, Jonas Passweg +3
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2103.08665
openalex publication_date 2021/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Tukey depth of a flat with respect to a point set is a concept that appears in many areas of discrete and computational geometry. In particular, the study of centerpoints, center transversals, Ham Sandwich cuts, or k-edges can all be phrased in terms of depths of certain flats with respect to one or more point sets. In this work, we introduce the Tukey depth histogram of k-flats in ℝd with respect to a point set P, which is a vector Dk,d(P), whose i'th entry Dk,di(P) denotes the number of k-flats spanned by k+1 points of P that have Tukey depth i with respect to P. As our main result, we give a complete characterization of the depth histograms of points, that is, for any dimension d we give a description of all possible histograms D0,d(P). This then allows us to compute the exact number of possible such histograms.