Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-257-90

Authors:

Chazelle, Bernard [1] / Edelsbrunner, Herbert [2] / Guibas, Leonidas [3] / Hershberger, John [4] / Seidel, Raimund [5] / Sharir, Micha [6]

Date:

March 1990

Pages:

20

Download Formats:

[PDF [7]]

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.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/283

[2] http://www.cs.princeton.edu/research/techreps/author/404

[3] http://www.cs.princeton.edu/research/techreps/author/417

[4] http://www.cs.princeton.edu/research/techreps/author/424

[5] http://www.cs.princeton.edu/research/techreps/author/718

[6] http://www.cs.princeton.edu/research/techreps/author/461

[7] ftp://ftp.cs.princeton.edu/techreports/1990/257.pdf