# 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, Herbert

^{ISTA}^{}; 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

Publisher

ACM

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.98551Chazelle, 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.98551Chazelle, 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, 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.