Slimming Down by Adding: Selecting Heavily Covered Points

Abstract:

We show that for any set P of n points in three-dimentional space there is a set Q of O(n1/2 log3 n) points so that the Delaunay triangulation of P union Q has at most O(n3/2 log3 n) edges - even though the Delaunay triangulation of P may have omega(n2) edges. The main tool of our construction is the following geometric covering result: For any set P of n points in three-dimensional space and any set S of m spheres, where each sphere passes through a distinct point pair in P, there exists a point x, not necessarily in P, that is enclosed by
omega (m2/ n2 log6 (n2/m)) of the spheres in S. Our results generalize to arbitrary fixed dimensions, to geometric bodies other than sphere, and to geometric structures other than Delaunay triangulations.