Abstract
The following result was proved by Bárány in 1982: For every d≥1, there exists c d >0 such that for every n-point set S in ℝd, there is a point p∈ℝd contained in at least c d n d+1−O(n d) of the d-dimensional simplices spanned by S.
We investigate the largest possible value of c d . It was known that c d ≤1/(2d(d+1)!) (this estimate actually holds for every point set S). We construct sets showing that c d ≤(d+1)−(d+1), and we conjecture that this estimate is tight. The best known lower bound, due to Wagner, is c d ≥γ d :=(d 2+1)/((d+1)!(d+1)d+1); in his method, p can be chosen as any centerpoint of S. We construct n-point sets with a centerpoint that is contained in no more than γ d n d+1+O(n d) simplices spanned by S, thus showing that the approach using an arbitrary centerpoint cannot be further improved.
We also prove that for every n-point set S⊂ℝd, there exists a (d−2)-flat that stabs at least c d,d−2 n 3−O(n 2) of the triangles spanned by S, with \(c_{d,d-2}\ge\frac{1}{24}(1-1/(2d-1)^{2})\) . To this end, we establish an equipartition result of independent interest (generalizing planar results of Buck and Buck and of Ceder): Every mass distribution in ℝd can be divided into 4d−2 equal parts by 2d−1 hyperplanes intersecting in a common (d−2)-flat.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alon, N., Bárány, I., Füredi, Z., Kleitman, D.J.: Point selections and weak ε-nets for convex hulls. Comb. Probab. Comput. 1, 189–200 (1992). http://www.math.tau.ac.il/~nogaa/PDFS/abfk3.pdf
Bárány, I.: A generalization of Carathéodory’s theorem. Discrete Math. 40, 141–152 (1982)
Bárány, I., Füredi, Z., Lovász, L.: On the number of halving planes. Combinatorica 10(2), 175–183 (1990). http://www.cs.elte.hu/~lovasz/morepapers/halvingplane.pdf
Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry, 2nd edn. Algorithms and Computation in Mathematics, vol. 10. Springer, Berlin (2006)
Buck, R.C., Buck, E.F.: Equipartition of convex sets. Math. Mag. 22, 195–198 (1948–1949)
Boros, E., Füredi, Z.: Su un teorema di Kárteszi nella geometria combinatoria. Archimede 2, 71–76 (1977)
Boros, E., Füredi, Z.: The number of triangles covering the center of an n-set. Geom. Dedic. 17, 69–77 (1984)
Bukh, B.: A point in many triangles. Electron. J. Combin. 13(1), Note 10, 3 pp. (2006), (electronic)
Ceder, J.G.: Generalized sixpartite problems. Bol. Soc. Mat. Mex. (2) 9, 28–32 (1964)
Dey, T.K., Edelsbrunner, H.: Counting triangle crossings and halving planes. Discrete Comput. Geom. 12(1), 281–289 (1994)
Eppstein, D.: Improved bounds for intersecting triangles and halving planes. J. Comb. Theory Ser. A 62(1), 176–182 (1993). http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-91-60.pdf
Fadell, E.R.: Ideal-valued generalizations of Ljusternik–Schnierelmann category, with applications. In: Fadell, E., et al. (eds.) Topics in Equivariant Topology. Sém. Math. Sup., vol. 108, pp. 11–54. Press Univ. Montréal, Montréal (1989)
Fadell, E.R., Husseini, S.: An ideal-valued cohomological index theory with applications to Borsuk–Ulam and Bourgin–Yang theorems. Ergod. Theory Dynam. Sys. 8, 73–85 (1988)
Inoue, A.: Borsuk-Ulam type theorems on Stiefel manifolds. Osaka J. Math. 43(1), 183–191 (2006). http://projecteuclid.org/euclid.ojm/1146243001
Kárteszi, F.: Extremalaufgaben über endliche Punktsysteme. Publ. Math. (Debr.) 4, 16–27 (1955)
Matoušek, J.: Lectures on Discrete Geometry. Springer, New York (2002)
Matoušek, J.: Using the Borsuk–Ulam Theorem. Springer, Berlin (2008). Revised 2nd printing
Moon, J.W.: Topics on Tournaments. Holt, Rinehart and Winston, New York (1968)
Nivasch, G., Sharir, M.: Eppstein’s bound on intersecting triangles revisited. J. Comb. Theory Ser. A 116(2), 494–497 (2009). arXiv:0804.4415
Rado, R.: A theorem on general measure. J. Lond. Math. Soc. 21, 291–300 (1947)
Smorodinsky, S.: Combinatorial problems in computational geometry. Ph.D. thesis, Tel Aviv University, June 2003. http://www.cs.bgu.ac.il/~shakhar/my_papers/phd.ps.gz
Wagner, U.: On k-sets and applications. Ph.D. thesis, ETH Zürich, June 2003. http://www.inf.ethz.ch/~emo/DoctThesisFiles/wagner03.pdf
Welzl, E.: Entering and leaving j-facets. Discrete Comput. Geom. 25, 351–364 (2001). http://www.inf.ethz.ch/personal/emo/PublFiles/EnterLeave_DCG25_01.ps
Wendel, J.G.: A problem in geometric probability. Math. Scand. 11, 109–111 (1962)
Živaljević, R.T.: User’s guide to equivariant methods in combinatorics II. Publ. Inst. Math. (Beogr.) 64(78), 107–132 (1998)
Živaljević, R.T.: Topological methods. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn. CRC Press, Boca Raton (2004). Chap. 14
Živaljević, R.T., Vrećica, S.T.: The colored Tverberg’s problem and complexes of injective functions. J. Comb. Theory Ser. A 61(2), 309–318 (1992)
Author information
Authors and Affiliations
Corresponding author
Additional information
Work by B. Bukh was partially carried out at Tel Aviv University.
Work by G. Nivasch was supported by ISF Grant 155/05 and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University.
Rights and permissions
About this article
Cite this article
Bukh, B., Matoušek, J. & Nivasch, G. Stabbing Simplices by Points and Flats. Discrete Comput Geom 43, 321–338 (2010). https://doi.org/10.1007/s00454-008-9124-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-008-9124-4