Slimming down by adding; selecting heavily covered points

B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, in:, ACM, 1990, pp. 116–127.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
; ; ; ; ;
Abstract
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
Page
116 - 127
Conference
SCG: Symposium on Computational Geometry
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: 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 (pp. 116–127). Presented at the SCG: Symposium on Computational Geometry, 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,” 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,” presented at the SCG: Symposium on Computational Geometry, 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. SCG: Symposium on Computational Geometry 116–127.
Chazelle, Bernard, et al. Slimming down by Adding; Selecting Heavily Covered Points. ACM, 1990, pp. 116–27, doi:10.1145/98524.98551.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar