Tukey Depth Histograms
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Combinatorial representations of point sets play an important role in discrete and computational geometry. In this work, we investigate a new combinatorial quantity of a point set, called Tukey depth histogram. The Tukey depth histogram of k-flats in Rd with respect to a point set P, is a vector Dk,d(P), whose i’th entry Dik,d(P) denotes the number of k-flats spanned by k+ 1 points of P that have Tukey depth i with respect to P. It turns out that several problems in discrete and computational geometry can be phrased in terms of such depth histograms. 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 different histograms of points.
Original language | English |
---|---|
Title of host publication | Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings |
Editors | Cristina Bazgan, Henning Fernau |
Publisher | Springer |
Publication date | 2022 |
Pages | 186-198 |
ISBN (Print) | 9783031066771 |
DOIs | |
Publication status | Published - 2022 |
Event | 33rd International Workshop on Combinatorial Algorithms, IWOCA 2022 - Trier, Germany Duration: 7 Jun 2022 → 9 Jun 2022 |
Conference
Conference | 33rd International Workshop on Combinatorial Algorithms, IWOCA 2022 |
---|---|
Land | Germany |
By | Trier |
Periode | 07/06/2022 → 09/06/2022 |
Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 13270 LNCS |
ISSN | 0302-9743 |
Bibliographical note
Publisher Copyright:
© 2022, Springer Nature Switzerland AG.
- Computational geometry, Depth statistics, Point sets, Tukey depth
Research areas
Links
- https://arxiv.org/pdf/2103.08665.pdf
Submitted manuscript
ID: 318801524