Document Open Access Logo

Barycentric Cuts Through a Convex Body

Authors Zuzana Patáková , Martin Tancer, Uli Wagner

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2020.62.pdf
  • Filesize: 0.71 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • convex body
  • barycenter
  • Tukey depth
  • smooth manifold
  • critical points

Metrics

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

Abstract

Let K be a convex body in ℝⁿ (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K ∩ h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p₀ is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question.
It follows from known results that for n ≥ 2, there are always at least three distinct barycentric cuts through the point p₀ ∈ K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p₀ are guaranteed if n ≥ 3.

Cite As Get BibTex

Zuzana Patáková, Martin Tancer, and Uli Wagner. Barycentric Cuts Through a Convex Body. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SoCG.2020.62

Author Details

Zuzana Patáková
  • Computer Science Institute, Charles University, Prague, Czech Republic
  • IST Austria, Klosterneuburg, Austria
Martin Tancer
  • Department of Applied Mathematics, Charles University, Prague, Czech Republic
Uli Wagner
  • IST Austria, Klosterneuburg, Austria

Funding

  • Patáková, Zuzana: The research stay at IST Austria is funded by the project Improvement of internationalization (CZ.02.2.69/0.0/0.0/17_050/0008466) in the field of research and development at Charles University, through the support of quality projects MSCA-IF.
  • Tancer, Martin: Supported by the GAČR grant 19-04113Y and by the Charles University projects PRIMUS/17/SCI/3 and UNCE/SCI/004.

Acknowledgements

We thank Stanislav Nagy for introducing us to Grünbaum’s questions, for useful discussions on the topic, for providing us with many references, and for comments on a preliminary version of this paper. We thank Jan Kynčl and Pavel Valtr for letting us know about a more general counterexample they found, and Roman Karasev for pointing us to related work [R. Karasev, 2011; P. Blagojević and R. Karasev, 2016] and for comments on a preliminary version of this paper. Finally, we thank an anonymous referee for many comments on a preliminary version of the paper which, in particular, yielded an important correction in Section 4.

References

  1. P. Blagojević and R. Karasev. Local multiplicity of continuous maps between manifolds, 2016. Preprint. URL: http://arxiv.org/abs/1603.06723.
  2. W. Blaschke. Über affine Geometrie IX: Verschiedene Bemerkungen und Aufgaben. Ber. Verh. Sächs. Akad. Wiss. Leipzig. Math.-Nat. Kl., 69:412-420, 1917. Google Scholar
  3. D. Bremner, D. Chen, J. Iacono, S. Langerman, and P. Morin. Output-sensitive algorithms for Tukey depth and related problems. Stat. Comput., 18(3):259-266, 2008. URL: https://doi.org/10.1007/s11222-008-9054-2.
  4. T. M. Chan. An optimal randomized algorithm for maximum Tukey depth. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 430-436. ACM, New York, 2004. Google Scholar
  5. D. Chen, P. Morin, and U. Wagner. Absolute approximation of Tukey depth: theory and experiments. Comput. Geom., 46(5):566-573, 2013. URL: https://doi.org/10.1016/j.comgeo.2012.03.001.
  6. H. T. Croft, K. J. Falconer, and R. K. Guy. Unsolved problems in geometry. Problem Books in Mathematics. Springer-Verlag, New York, 1994. Corrected reprint of the 1991 original, Unsolved Problems in Intuitive Mathematics, II. Google Scholar
  7. D. L. Donoho. Breakdown properties of multivariate location estimators, 1982. Unpublished qualifying paper, Harvard University. Google Scholar
  8. D. L. Donoho and M. Gasko. Breakdown properties of location estimates based on halfspace depth and projected outlyingness. Ann. Statist., 20(4):1803-1827, 1992. URL: https://doi.org/10.1214/aos/1176348890.
  9. C. Dupin. Applications de géométrie et de méchanique, a la marine, aux ponts et chaussées, etc., pour faire suite aux Développements de géométrie, par Charles Dupin. Bachelier, successeur de Mme. Ve. Courcier, libraire, 1822. Google Scholar
  10. R. Dyckerhoff and P. Mozharovskyi. Exact computation of the halfspace depth. Comput. Statist. Data Anal., 98:19-30, 2016. URL: https://doi.org/10.1016/j.csda.2015.12.011.
  11. B. Grünbaum. On some properties of convex sets. Colloq. Math., 8:39-42, 1961. URL: https://doi.org/10.4064/cm-8-1-39-42.
  12. B. Grünbaum. Measures of symmetry for convex sets. In Proc. Sympos. Pure Math., Vol. VII, pages 233-270. Amer. Math. Soc., Providence, R.I., 1963. Google Scholar
  13. A. Hassairi and O. Regaieg. On the Tukey depth of a continuous probability distribution. Statist. Probab. Lett., 78(15):2308-2313, 2008. Google Scholar
  14. A. Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002. Google Scholar
  15. R. Karasev. Geometric coincidence results from multiplicity of continuous maps, 2011. Preprint. URL: http://arxiv.org/abs/1106.6176.
  16. J. Kynčl and P. Valtr, 2019. Personal communication. Google Scholar
  17. X. Liu, K. Mosler, and P. Mozharovskyi. Fast computation of Tukey trimmed regions and median in dimension p>2. J. Comput. Graph. Statist., 28(3):682-697, 2019. URL: https://doi.org/10.1080/10618600.2018.1546595.
  18. S. Nagy, C. Schütt, and E. M. Werner. Halfspace depth and floating body. Stat. Surv., 13:52-118, 2019. Google Scholar
  19. Z. Patáková, M. Tancer, and U. Wagner. Barycentric cuts through a convex body, 2020. Preprint. URL: http://arxiv.org/abs/2003.13536.
  20. P. J. Rousseeuw and I. Ruts. The depth function of a population distribution. Metrika, 49(3):213-244, 1999. Google Scholar
  21. P. J. Rousseeuw and A. Struyf. Computing location depth and regression depth in higher dimensions. Statistics and Computing, 8(3):193-203, 1998. Google Scholar
  22. C. Schütt and E. Werner. Homothetic floating bodies. Geom. Dedicata, 49(3):335-348, 1994. Google Scholar
  23. J. Tukey. Mathematics and the picturing of data. In Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974), Vol. 2, pages 523-531, 1975. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact