Slimming down by adding; selecting heavily covered points

ABSTRACT

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

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Verification