Document Open Access Logo

Enclosing Depth and Other Depth Measures

Author Patrick Schnider

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.10.pdf
  • Filesize: 0.82 MB
  • 15 pages

Document Identifiers

Author Details

Patrick Schnider
  • Department of Mathematical Sciences, University of Copenhagen, Denmark

Funding

The author has received funding from the European Research Council under the European Unions Seventh Framework Programme ERC Grant agreement ERC StG 716424 - CASe.

Acknowledgements

Thanks to Emo Welzl, Karim Adiprasito and Uli Wagner for the helpful discussions.

Cite AsGet BibTex

Patrick Schnider. Enclosing Depth and Other Depth Measures. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.10

Abstract

We study families of depth measures defined by natural sets of axioms. We show that any such depth measure is a constant factor approximation of Tukey depth. We further investigate the dimensions of depth regions, showing that the Cascade conjecture, introduced by Kalai for Tverberg depth, holds for all depth measures which satisfy our most restrictive set of axioms, which includes Tukey depth. Along the way, we introduce and study a new depth measure called enclosing depth, which we believe to be of independent interest, and show its relation to a constant-fraction Radon theorem on certain two-colored point sets.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Depth measures
  • Tukey depth
  • Tverberg theorem
  • Combinatorial Geometry

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Greg Aloupis. Geometric measures of data depth. In Data Depth: Robust Multivariate Analysis, Computational Geometry and Applications, pages 147-158, 2003. URL: https://doi.org/10.1090/dimacs/072/10.
  2. Edoardo Amaldi and Viggo Kann. The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoretical Computer Science, 147(1):181-210, 1995. Google Scholar
  3. David Avis. The m-core properly contains the m-divisible points in space. Pattern recognition letters, 14(9):703-705, 1993. Google Scholar
  4. Imre Bárány and Pablo Soberón. Tverberg’s theorem is 50 years old: a survey. Bulletin of the American Mathematical Society, 55(4):459-492, 2018. Google Scholar
  5. Imre Bárány and Pavel Valtr. A positive fraction Erdös-Szekeres theorem. Discrete & Computational Geometry, 19(3):335-342, 1998. Google Scholar
  6. DG Bourgin. On some separation and mapping theorems. Commentarii Mathematici Helvetici, 29(1):199-214, 1955. Google Scholar
  7. Dan Chen, Pat Morin, and Uli Wagner. Absolute approximation of Tukey depth: Theory and experiments. Computational Geometry, 46(5):566-573, 2013. Geometry and Optimization. Google Scholar
  8. VL Dol'nikov. Transversals of families of sets in in ℝⁿ and a connection between the Helly and Borsuk theorems. Russian Academy of Sciences. Sbornik Mathematics, 79(1):93, 1994. Google Scholar
  9. Jacob Fox, János Pach, and Andrew Suk. A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing. SIAM Journal on Computing, 45(6):2199-2223, 2016. Google Scholar
  10. Sariel Har-Peled and Timothy Zhou. Improved approximation algorithms for tverberg partitions. arXiv preprint, 2020. URL: http://arxiv.org/abs/2007.08717.
  11. Joseph L Hodges. A bivariate sign test. The Annals of Mathematical Statistics, 26(3):523-527, 1955. Google Scholar
  12. D.S. Johnson and F.P. Preparata. The densest hemisphere problem. Theoretical Computer Science, 6(1):93-107, 1978. Google Scholar
  13. GIL KALAI. Combinatorics with a geometric flavor. Visions in Mathematics: GAFA 2000 Special Volume, Part II, page 742, 2011. Google Scholar
  14. Gil Kalai. Problems in geometric and topological combinatorics. Lecture at FU Berlin, 2011. Google Scholar
  15. Gil Kalai. Problems for imre bárány’s birthday. Discrete Geometry and Convexity in Honour of Imre Bárány, page 59, 2017. Google Scholar
  16. R. Y. Liu. On a notion of data depth based on random simplices. The Annals of Statistics, 18(1):405-414, 1990. Google Scholar
  17. Regina Y. Liu, Jesse M. Parelius, and Kesar Singh. Multivariate analysis by data depth: descriptive statistics, graphics and inference. Ann. Statist., 27(3):783-858, June 1999. Google Scholar
  18. Jiří Matoušek. Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. Springer Publishing Company, Incorporated, 2007. Google Scholar
  19. Jivr'i Matouvsek. Lectures on discrete geometry, volume 212 of Graduate texts in mathematics. Springer, 2002. Google Scholar
  20. Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, J. Antoni Sellarès, Diane Souvaine, Ileana Streinu, and Anja Struyf. Efficient computation of location depth contours by methods of computational geometry. Statistics and Computing, 13(2):153-162, 2003. Google Scholar
  21. Karl Mosler. Depth Statistics, pages 17-34. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. Google Scholar
  22. Richard Rado. A theorem on general measure. Journal of the London Mathematical Society, 21:291-300, 1947. Google Scholar
  23. John R Reay. Several generalizations of tverberg’s theorem. Israel Journal of Mathematics, 34(3):238-244, 1979. Google Scholar
  24. Jean-Pierre Roudneff. Partitions of points into simplices withk-dimensional intersection. part i: The conic tverberg’s theorem. European Journal of Combinatorics, 22(5):733-743, 2001. Google Scholar
  25. Jean-Pierre Roudneff. Partitions of points into simplices withk-dimensional intersection. part ii: Proof of reay’s conjecture in dimensions 4 and 5. European Journal of Combinatorics, 22(5):745-765, 2001. Google Scholar
  26. Jean-Pierre Roudneff. New cases of reay’s conjecture on partitions of points into simplices with k-dimensional intersection. European Journal of Combinatorics, 30(8):1919-1943, 2009. Google Scholar
  27. Csaba D Toth, Joseph O'Rourke, and Jacob E Goodman. Handbook of discrete and computational geometry. Chapman and Hall/CRC, 2017. Google Scholar
  28. John W. Tukey. Mathematics and the picturing of data. In Proc. International Congress of Mathematicians, pages 523-531, 1975. Google Scholar
  29. Helge Tverberg. A generalization of Radon’s theorem. Journal of the London Mathematical Society, 1(1):123-128, 1966. Google Scholar
  30. Chung-Tao Yang. On theorems of Borsuk-Ulam, Kakutani-Yamabe-Yujobô and Dyson, I. Annals of Mathematics, pages 262-282, 1954. Google Scholar
  31. Rade T. Zivaljević and Siniša T Vrećica. An extension of the ham sandwich theorem. Bulletin of the London Mathematical Society, 22(2):183-186, 1990. Google Scholar
  32. Yijun Zuo and Robert Serfling. Structural properties and convergence results for contours of sample statistical depth functions. Ann. Statist., 28(2):483-499, April 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact