Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Barycentric Cuts Through a Convex Body

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

Let K be a convex body in \(\mathbb {R}^n\) (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 \cap 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_0\) 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 \ge 2\), there are always at least three distinct barycentric cuts through the point \(p_0 \in K\) of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through \(p_0\) are guaranteed if \(n \ge 3\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. Given \(v, v' \in S^{n-1}\), \(\lambda (H_v \cap K)\) and \(\lambda (H_{v'} \cap K)\) differ by at most \(\lambda ((H_v \Delta H_{v'})\cap K)\) where \(\Delta \) is the symmetric difference. For \(\varepsilon > 0\) and v and \(v'\) sufficiently close, \(\lambda ((H_v \Delta H_{v'}) \cap K) < \varepsilon \lambda (K)\) as K is bounded.

  2. We remark that our depth function slightly differs from the function f(Hp) used by Grünbaum [12, § 6.2]. However, the point of maximal depth coincides with the ‘critical point’ in [12] and hyperplanes realizing the depth for \(p_0\) coincide with the ‘hyperplanes through the critical point dividing the volume of K in the ratio \(F_2(K)\)’.

  3. The idea of the proof is simple: For contradiction assume that h realizes the depth of p but that the barycenter b of \(K \cap h\) differs from p. Let \(v \in S^{n-1}\) be such that \(h = h_v\) and \({{\,\mathrm{depth}\,}}(p, K) = \delta ^p(v)\). Consider the affine \((d-2)\)-space \(\rho \) in h passing through p and perpendicular to the segment bp. Then by a small rotation of h along \(\rho \) we can get \(h_{v'}\) such that \(\delta ^p(v') < \delta ^p(v)\) which contradicts that h realizes the depth of p. Of course, it remains to check the details.

  4. We remark that the second condition in the statement of the result in [19] is equivalent to the statement that \(0 \in {{\,\mathrm{conv}\,}}U\), in our notation.

  5. Sketch of the inverse ray basis theorem: if there is a closed hemisphere \(C \subseteq S^{n-1}\) which does not contain a point of U, let v be the center of C. Then a small shift of \(p_0\) in the direction of v yields a point of larger depth, a contradiction.

  6. When compared with formula (3.1) in [13], we obtain a different sign in front of the integral. This is caused by integration over the opposite halfspace.

  7. By a metric ball we mean a ball with a given center and radius. This way, we distinguish a metric ball from a general topological ball.

  8. We point out that the current online version of [14] contains a different proof of Proposition 1.14. Therefore, here we refer to the printed version of the book.

References

  1. Blagojević, P.V.M., Karasev, R.: Local multiplicity of continuous maps between manifolds (2016). arXiv:1603.06723

  2. Blaschke, W.: Über affine Geometrie IX: Verschiedene Bemerkungen und Aufgaben. Berichte Verh. Sächs. Ges. Wiss. Leipzig Math.-Phys. Cl. 69, 412–420 (1917)

    MATH  Google Scholar 

  3. Bremner, D., Chen, D., Iacono, J., Langerman, S., Morin, P.: Output-sensitive algorithms for Tukey depth and related problems. Stat. Comput. 18(3), 259–266 (2008)

    Article  MathSciNet  Google Scholar 

  4. Chan, T.M.: An optimal randomized algorithm for maximum Tukey depth. In: 15th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2004), pp. 430–436. ACM, New York (2004)

  5. Chen, D., Morin, P., Wagner, U.: Absolute approximation of Tukey depth: theory and experiments. Comput. Geom. 46(5), 566–573 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  6. Croft, H.T., Falconer, K.J., Guy, R.K.: Unsolved Problems in Geometry. Problem Books in Mathematics. Unsolved Problems in Intuitive Mathematics, vol. 2. Springer, New York (1994)

    MATH  Google Scholar 

  7. Donoho, D.L.: Breakdown properties of multivariate location estimators. Unpublished qualifying paper, Harvard University (1982)

  8. Donoho, D.L., Gasko, M.: Breakdown properties of location estimates based on halfspace depth and projected outlyingness. Ann. Stat. 20(4), 1803–1827 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  9. Dupin, C.: 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. Bachelier, Paris (1822)

  10. Dyckerhoff, R., Mozharovskyi, P.: Exact computation of the halfspace depth. Comput. Stat. Data Anal. 98, 19–30 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  11. Grünbaum, B.: On some properties of convex sets. Colloq. Math. 8, 39–42 (1961)

    Article  MathSciNet  MATH  Google Scholar 

  12. Grünbaum, B.: Measures of symmetry for convex sets. In: Proceedings of Symposia in Pure Mathematics, vol. 7. pp. 233–270. American Mathematical Society, Providence (1963)

  13. Hassairi, A., Regaieg, O.: On the Tukey depth of a continuous probability distribution. Stat. Probab. Lett. 78(15), 2308–2313 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  14. Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)

    MATH  Google Scholar 

  15. Karasev, R.N.: Geometric coincidence results from multiplicity of continuous maps (2011). arXiv:1106.6176

  16. Liu, X., Mosler, K., Mozharovskyi, P.: Fast computation of Tukey trimmed regions and median in dimension \({p>2}\). J. Comput. Graph. Stat. 28(3), 682–697 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  17. Munkres, J.: Topology. Pearson Education, Harlow (2014)

    MATH  Google Scholar 

  18. Nagy, S., Schütt, C., Werner, E.M.: Halfspace depth and floating body. Stat. Surv. 13, 52–118 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  19. Rousseeuw, P.J., Ruts, I.: The depth function of a population distribution. Metrika 49(3), 213–244 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  20. Rousseeuw, P.J., Struyf, A.: Computing location depth and regression depth in higher dimensions. Stat. Comput. 8(3), 193–203 (1998)

  21. Schütt, C., Werner, E.: Homothetic floating bodies. Geom. Dedicata 49(3), 335–348 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  22. Tukey, J.W.: Mathematics and the picturing of data. In: International Congress of Mathematicians (Vancouver 1974), vol. 2, pp. 523–531. Canadian Mathematical Society, Montreal (1975)

Download references

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. We thank Roman Karasev for providing us with references [1, 15] 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 Sect. 4.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Martin Tancer.

Additional information

Editor in Charge: Kenneth Clarkson

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The work by Zuzana Patáková has been partially supported by Charles University Research Center Program No. UNCE/SCI/022, and part of it was done during her research stay at IST Austria. The work by Martin Tancer is supported by the GAČR Grant 19-04113Y and by the Charles University Projects PRIMUS/17/SCI/3 and UNCE/SCI/004.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Patáková, Z., Tancer, M. & Wagner, U. Barycentric Cuts Through a Convex Body. Discrete Comput Geom 68, 1133–1154 (2022). https://doi.org/10.1007/s00454-021-00364-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-021-00364-7

Keywords

Mathematics Subject Classification

Navigation