Points and triangles in the plane and halving planes in space
Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. 1991. Points and triangles in the plane and halving planes in space. Discrete & Computational Geometry. 6(1), 435–442.
Download (ext.)
Journal Article
| Published
| English
Scopus indexed
Author
Aronov, Boris;
Chazelle, Bernard;
Edelsbrunner, HerbertISTA 
;
Guibas, Leonidas;
Sharir, Micha;
Wenger, Rephael
;
Guibas, Leonidas;
Sharir, Micha;
Wenger, RephaelAbstract
We prove that for any set S of n points in the plane and n3-α triangles spanned by the points in S there exists a point (not necessarily in S) contained in at least n3-3α/(c log5 n) of the triangles. This implies that any set of n points in three-dimensional space defines at most {Mathematical expression} halving planes.
Publishing Year
Date Published
1991-12-01
Journal Title
Discrete & Computational Geometry
Publisher
Springer
Acknowledgement
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
Volume
6
Issue
1
Page
435 - 442
ISSN
eISSN
IST-REx-ID
Cite this
Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. Points and triangles in the plane and halving planes in space. Discrete & Computational Geometry. 1991;6(1):435-442. doi:10.1007/BF02574700
Aronov, B., Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., & Wenger, R. (1991). Points and triangles in the plane and halving planes in space. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02574700
Aronov, Boris, Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Rephael Wenger. “Points and Triangles in the Plane and Halving Planes in Space.” Discrete & Computational Geometry. Springer, 1991. https://doi.org/10.1007/BF02574700.
B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and R. Wenger, “Points and triangles in the plane and halving planes in space,” Discrete & Computational Geometry, vol. 6, no. 1. Springer, pp. 435–442, 1991.
Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. 1991. Points and triangles in the plane and halving planes in space. Discrete & Computational Geometry. 6(1), 435–442.
Aronov, Boris, et al. “Points and Triangles in the Plane and Halving Planes in Space.” Discrete & Computational Geometry, vol. 6, no. 1, Springer, 1991, pp. 435–42, doi:10.1007/BF02574700.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar