TY - CONF
AB - 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.
AU - Chazelle, Bernard
AU - Edelsbrunner, Herbert
AU - Guibas, Leonidas
AU - Hershberger, John
AU - Seidel, Raimund
AU - Sharir, Micha
ID - 4078
SN - 978-0-89791-362-1
T2 - Proceedings of the 6th annual symposium on computational geometry
TI - Slimming down by adding; selecting heavily covered points
ER -