Abstract
Every collection oft≥2n 2 triangles with a total ofn vertices in ℝ3 has Ω(t 4/n 6) crossing pairs. This implies that one of their edges meets Ω(t 3/n 6) of the triangles. From this it follows thatn points in ℝ3 have onlyO(n 8/3) halving planes.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Ajtai, V. Chvátal, M. M. Newborn, and E. Szemerédi. Crossing-free subgraphs.Ann. Discrete Math. 12 (1982), 9–12.
N. Alon, I. Bárány, Z. Füredi, and D. J. Kleitman. Point selection and weak ε-nets for convex hulls.Combin. Probab. Comput. 1 (1992), 189–200.
B. Aronov, B. Chazelle, H. Edelsbrunner, L. J. Guibas, M. Sharir, and R. Wenger. Points and triangles in the plane and halving planes in space.Discrete Comput. Geom. 6 (1991), 435–442.
I. Bárány, Z. Füredi, and L. Lovász. On the number of halving planes.Proc. 5th Ann. Symp. on Computational Geometry, 1989, pp. 140–144.
H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, 1987.
D. Eppstein. Improved bounds for intersecting triangles and halving planes.J. Combin. Theory Ser. A 62 (1993), 176–182.
P. Erdős, L. Lovász, A. Simmons, and E. G. Straus. Dissection graphs of planar point sets. InA Survey of Combinatorial Theory, J. N. Srivastavaet al., eds., pp. 139–149, North-Holland, Amsterdam, 1973.
J. Radon. Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten.Math. Ann. 83 (1921), 113–115
R. Živaljević and S. Vrećica. The colored Tverberg’s problem and complexes of injective functions.J. Combin. Theory Ser. A 61 (1992), 309–318.
Author information
Authors and Affiliations
Additional information
The research of H. Edelsbrunner was supported by the National Science Foundation under Grant CCR-8921421 and under an Alan T. Waterman award, Grant CCR-9118874. Any opinions, findings and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the view of the National Science Foundation.
Rights and permissions
About this article
Cite this article
Dey, T.K., Edelsbrunner, H. Counting triangle crossings and halving planes. Discrete Comput Geom 12, 281–289 (1994). https://doi.org/10.1007/BF02574381
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574381