Document Open Access Logo

Combinatorial Depth Measures for Hyperplane Arrangements

Authors Patrick Schnider , Pablo Soberón

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.55.pdf
  • Filesize: 0.67 MB
  • 14 pages

Document Identifiers

Author Details

Patrick Schnider
  • Department of Computer Science, ETH Zürich, Switzerland
Pablo Soberón
  • Department of Mathematics, Baruch College, City University of New York, NY, USA
  • Department of Mathematics, The Graudate Center, City University of New York, NY, USA

Funding

  • Soberón, Pablo: Suppported by NSF DMS grant 2054419.

Cite As Get BibTex

Patrick Schnider and Pablo Soberón. Combinatorial Depth Measures for Hyperplane Arrangements. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SoCG.2023.55

Abstract

Regression depth, introduced by Rousseeuw and Hubert in 1999, is a notion that measures how good of a regression hyperplane a given query hyperplane is with respect to a set of data points. Under projective duality, this can be interpreted as a depth measure for query points with respect to an arrangement of data hyperplanes. The study of depth measures for query points with respect to a set of data points has a long history, and many such depth measures have natural counterparts in the setting of hyperplane arrangements. For example, regression depth is the counterpart of Tukey depth. Motivated by this, we study general families of depth measures for hyperplane arrangements and show that all of them must have a deep point. Along the way we prove a Tverberg-type theorem for hyperplane arrangements, giving a positive answer to a conjecture by Rousseeuw and Hubert from 1999. We also get three new proofs of the centerpoint theorem for regression depth, all of which are either stronger or more general than the original proof by Amenta, Bern, Eppstein, and Teng. Finally, we prove a version of the center transversal theorem for regression depth.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Combinatorics
Keywords
  • Depth measures
  • Hyperplane arrangements
  • Regression depth
  • Tverberg theorem

Metrics

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

Related Versions

References

  1. Nina Amenta, Marshall Bern, David Eppstein, and S H Teng. Regression depth and center points. Discrete & Computational Geometry, 23(3):305-323, 2000. Google Scholar
  2. 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
  3. Sergey Bereg, Ferran Hurtado, Mikio Kano, Matias Korman, Dolores Lara, Carlos Seara, Rodrigo I Silveira, Jorge Urrutia, and Kevin Verbeek. Balanced partitions of 3-colored geometric sets in the plane. Discrete Applied Mathematics, 181:21-32, January 2015. URL: https://doi.org/10.1016/j.dam.2014.10.015.
  4. J. P. Carvalho and P. Soberón. Counterexamples to the colorful Tverberg conjecture for hyperplanes. Acta Math. Hungar., 167(2):385-392, 2022. URL: https://doi.org/10.1007/s10474-022-01249-8.
  5. VL Dol'nikov. Transversals of families of sets in and a connection between the Helly and Borsuk theorems. Russian Academy of Sciences. Sbornik Mathematics, 79(1):93, 1994. Google Scholar
  6. Ruy Fabila-Monroy and Clemens Huemer. Carathéodory’s theorem in depth. Discrete Comput. Geom., 58(1):51-66, 2017. URL: https://doi.org/10.1007/s00454-017-9893-8.
  7. Radoslav Fulek, Andreas F. Holmsen, and János Pach. Intersecting Convex Sets by Rays. Discrete & Computational Geometry, 42(3):343-358, 2009. URL: https://doi.org/10.1007/s00454-009-9163-5.
  8. Sariel Har-Peled and Timothy Zhou. Improved Approximation Algorithms for Tverberg Partitions. arXiv preprint arXiv:2007.08717, 2020. Google Scholar
  9. Eduard Helly. Über Systeme abgeschlossener Mengen mit gemeinschaftlichen Punkten. Monatshefte d. Mathematik, 37:281-302, 1930. Google Scholar
  10. Roman N. Karasev. Tverberg’s Transversal Conjecture and Analogues of Nonembeddability Theorems for Transversals. Discrete & Computational Geometry, 38(3):513-525, December 2007. URL: https://doi.org/10.1007/s00454-007-1355-2.
  11. Roman N. Karasev. Dual theorems on central points and their generalizations. Sbornik: Mathematics, 199(10):1459-1479, 2008. URL: https://doi.org/10.1070/sm2008v199n10abeh003968.
  12. Roman N. Karasev. Tverberg-Type Theorems for Intersecting by Rays. Discrete & Computational Geometry, 45(2):340-347, 2011. URL: https://doi.org/10.1007/s00454-010-9294-8.
  13. Roman N. Karasev and Benjamin Matschke. Projective Center Point and Tverberg Theorems. Discrete & Computational Geometry, 52(1):88-101, 2014. URL: https://doi.org/10.1007/s00454-014-9602-9.
  14. Seunghun Lee and Kangmin Yoo. On a conjecture of Karasev. Comput. Geom., 75:1-10, 2018. URL: https://doi.org/10.1016/j.comgeo.2018.06.003.
  15. Ivan Mizera. On depth and deep points: a calculus. The Annals of Statistics, 30(6):1681-1736, 2002. Google Scholar
  16. János Pach. A Tverberg-type result on multicolored simplices. Computational Geometry, 10(2):71-76, 1998. URL: https://doi.org/10.1016/s0925-7721(97)00022-9.
  17. Richard Rado. A Theorem on General Measure. Journal of the London Mathematical Society, s1-21(4):291-300, 1946. URL: https://doi.org/10.1112/jlms/s1-21.4.291.
  18. Edgardo Roldán-Pensado and Pablo Soberón. A survey of mass partitions. Bull. Amer. Math. Soc. (N.S.), 59(2):227-267, 2022. URL: https://doi.org/10.1090/bull/1725.
  19. David Rolnick and Pablo Soberón. Algorithms for Tverberg’s theorem via centerpoint theorems. arXiv preprint arXiv:1601.03083, 2016. Google Scholar
  20. Jean-Pierre Roudneff. Partitions of points into simplices with k-dimensional intersection. part I: The conic Tverberg’s theorem. European Journal of Combinatorics, 22(5):733-743, 2001. Google Scholar
  21. Peter J. Rousseeuw and Mia Hubert. Depth in an arrangement of hyperplanes. Discrete & Computational Geometry, 22(2):167-176, 1999. Google Scholar
  22. Peter J. Rousseeuw and Mia Hubert. Regression depth. J. Amer. Statist. Assoc., 94(446):388-433, 1999. With discussion and a reply by the authors and Stefan Van Aelst. URL: https://doi.org/10.2307/2670155.
  23. Patrick Schnider. Enclosing depth and other depth measures. arXiv preprint arXiv:2103.08421, 2021. Google Scholar
  24. Patrick Schnider and Pablo Soberón. Combinatorial depth measures for hyperplane arrangements, 2023. URL: https://doi.org/10.48550/ARXIV.2302.07768.
  25. John W. Tukey. Mathematics and the picturing of data. In Proc. International Congress of Mathematicians, pages 523-531, 1975. Google Scholar
  26. Helge Tverberg. A generalization of Radon’s theorem. J. London Math. Soc, 41(1):123-128, 1966. Google Scholar
  27. Helge Tverberg and Siniša T. Vrećica. On Generalizations of Radon’s Theorem and the Ham Sandwich Theorem. European Journal of Combinatorics, 14(3):259-264, 1993. URL: https://doi.org/10.1006/eujc.1993.1029.
  28. Marc van Kreveld, Joseph S. B. Mitchell, Peter Rousseeuw, Micha Sharir, Jack Snoeyink, and Bettina Speckmann. Efficient algorithms for maximum regression depth. Discrete Comput. Geom., 39(4):656-677, 2008. URL: https://doi.org/10.1007/s00454-007-9046-6.
  29. Rade T. Živaljević 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
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 About DROPS Imprint Privacy Contact