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\).
Similar content being viewed by others
Notes
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.
We remark that our depth function slightly differs from the function f(H, p) 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)\)’.
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.
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.
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.
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.
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.
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
Blagojević, P.V.M., Karasev, R.: Local multiplicity of continuous maps between manifolds (2016). arXiv:1603.06723
Blaschke, W.: Über affine Geometrie IX: Verschiedene Bemerkungen und Aufgaben. Berichte Verh. Sächs. Ges. Wiss. Leipzig Math.-Phys. Cl. 69, 412–420 (1917)
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)
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)
Chen, D., Morin, P., Wagner, U.: Absolute approximation of Tukey depth: theory and experiments. Comput. Geom. 46(5), 566–573 (2013)
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)
Donoho, D.L.: Breakdown properties of multivariate location estimators. Unpublished qualifying paper, Harvard University (1982)
Donoho, D.L., Gasko, M.: Breakdown properties of location estimates based on halfspace depth and projected outlyingness. Ann. Stat. 20(4), 1803–1827 (1992)
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)
Dyckerhoff, R., Mozharovskyi, P.: Exact computation of the halfspace depth. Comput. Stat. Data Anal. 98, 19–30 (2016)
Grünbaum, B.: On some properties of convex sets. Colloq. Math. 8, 39–42 (1961)
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)
Hassairi, A., Regaieg, O.: On the Tukey depth of a continuous probability distribution. Stat. Probab. Lett. 78(15), 2308–2313 (2008)
Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)
Karasev, R.N.: Geometric coincidence results from multiplicity of continuous maps (2011). arXiv:1106.6176
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)
Munkres, J.: Topology. Pearson Education, Harlow (2014)
Nagy, S., Schütt, C., Werner, E.M.: Halfspace depth and floating body. Stat. Surv. 13, 52–118 (2019)
Rousseeuw, P.J., Ruts, I.: The depth function of a population distribution. Metrika 49(3), 213–244 (1999)
Rousseeuw, P.J., Struyf, A.: Computing location depth and regression depth in higher dimensions. Stat. Comput. 8(3), 193–203 (1998)
Schütt, C., Werner, E.: Homothetic floating bodies. Geom. Dedicata 49(3), 335–348 (1994)
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)
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
Corresponding author
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
About this article
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
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-021-00364-7