Slimming down by adding; selecting heavily covered points
Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. 1990. Slimming down by adding; selecting heavily covered points. Proceedings of the 6th annual symposium on computational geometry. SCG: Symposium on Computational Geometry, 116–127.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Chazelle, Bernard;
Edelsbrunner, HerbertISTA 
;
Guibas, Leonidas;
Hershberger, John;
Seidel, Raimund;
Sharir, Micha
;
Guibas, Leonidas;
Hershberger, John;
Seidel, Raimund;
Sharir, MichaAbstract
In this paper we derived combinatorial point selection results for geometric objects defined by pairs of points. In a nutshell, the results say that if many pairs of a set of n points in some fixed dimension each define a geometric object of some type, then there is a point covered by many of these objects. Based on such a result for three-dimensional spheres we show that the combinatorial size of the Delaunay triangulation of a point set in space can be reduced by adding new points. We believe that from a practical point of view this is the most important result of this paper.
Publishing Year
Date Published
1990-01-01
Proceedings Title
Proceedings of the 6th annual symposium on computational geometry
Page
116 - 127
Conference
SCG: Symposium on Computational Geometry
Conference Location
Berkley, CA, United States
Conference Date
1990-06-07 – 1990-06-09
ISBN
IST-REx-ID
Cite this
Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. Slimming down by adding; selecting heavily covered points. In: Proceedings of the 6th Annual Symposium on Computational Geometry. ACM; 1990:116-127. doi:10.1145/98524.98551
Chazelle, B., Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., & Sharir, M. (1990). Slimming down by adding; selecting heavily covered points. In Proceedings of the 6th annual symposium on computational geometry (pp. 116–127). Berkley, CA, United States: ACM. https://doi.org/10.1145/98524.98551
Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, John Hershberger, Raimund Seidel, and Micha Sharir. “Slimming down by Adding; Selecting Heavily Covered Points.” In Proceedings of the 6th Annual Symposium on Computational Geometry, 116–27. ACM, 1990. https://doi.org/10.1145/98524.98551.
B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, and M. Sharir, “Slimming down by adding; selecting heavily covered points,” in Proceedings of the 6th annual symposium on computational geometry, Berkley, CA, United States, 1990, pp. 116–127.
Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. 1990. Slimming down by adding; selecting heavily covered points. Proceedings of the 6th annual symposium on computational geometry. SCG: Symposium on Computational Geometry, 116–127.
Chazelle, Bernard, et al. “Slimming down by Adding; Selecting Heavily Covered Points.” Proceedings of the 6th Annual Symposium on Computational Geometry, ACM, 1990, pp. 116–27, doi:10.1145/98524.98551.
Google Scholar
ISBN Search