Abstract
We prove that for any setS ofn points in the plane andn 3−α triangles spanned by the points inS there exists a point (not necessarily inS) contained in at leastn 3−3α/(c log5 n) of the triangles. This implies that any set ofn points in three-dimensional space defines at most\(\sqrt[3]{{(c/2)}}n^{8/3} \log ^{5/3} n\) halving planes.
Article PDF
Similar content being viewed by others
References
N. Alon and E. Györi. The number of small semispaces of a finite set of points in the plane.J. Combin. Theory Ser. A 41 (1986), 154–157.
F. Aurenhammer, Power diagrams: properties, algorithms, and applications,SIAM J. Comput. 16 (1987), 78–96.
I. Bárány. A generalization of Carathéodory's theorem.Discrete Math. 40 (1982), 141–152.
I. Bárány, Z. Füredi and L. Lovász. On the number of halving planes. InProc. Fifth Ann. Symp. Comput. Geom., 1989, pp. 140–144.
E. Boros and Z. Füredi. The number of triangles covering the center of ann-set.Geom. Dedicata 17 (1984), 69–77.
B. Chazelle, H. Edelsbrunner, L. J. Guibas, J. Hershberger, R. Seidel, and M. Sharir. Slimming down by adding; selecting heavily covered points. InProc. Sixth Ann. Symp. Comput. Geom., 1990, pp. 116–127.
K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II.Discrete Comput. Geom. 4 (1989), 387–421.
H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, 1987.
H. Edelsbrunner and E. Welzl. On the number of line separations of a finite set in the plane.J. Combin. Theory Ser. A 38 (1985), 15–29.
P. Erdös, L. Lovász, A. Simmons and E. G. Strauss. Dissection graphs of planar point sets. InA Survey of Combinatorial Theory, J. N. Srivastavaet al., eds., 1973, pp. 139–149, North-Holland, Amsterdam.
J.E. Goodman and R. Pollack. On the number ofk-subsets of a set ofn points in the plane.J. Combin. Theory Ser. A 36 (1984), 101–104.
J. Pach, W. Steiger, and E. Szemerédi. An upper bound on the number of planark-sets. InProc. 30th ann. IEEE Symp. Found. Comput. Sci., 1989, pp. 72–79.
Author information
Authors and Affiliations
Additional information
Work on this paper by Boris Aronov and Rephael Wenger has been supported by DIMACS under NSF Grant STC-88-09648. Work on this paper by Bernard Chazelle has been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrunner has been supported by NSF Grant CCR-87-14565. Micha Sharir has been supported by ONR Grant N00014-87-K-0129, by NSF Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Israeli National Council for Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.
Rights and permissions
About this article
Cite this article
Aronov, B., Chazelle, B., Edelsbrunner, H. et al. Points and triangles in the plane and halving planes in space. Discrete Comput Geom 6, 435–442 (1991). https://doi.org/10.1007/BF02574700
Received:
Revised:
Published:
Issue date:
DOI: https://doi.org/10.1007/BF02574700
