Slimming down by adding; selecting heavily covered points
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.
116 - 127
116 - 127
ACM