Slimming down by adding; selecting heavily covered points
Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, John E. Hershberger, Raimund Seidel, Micha Sharir · 1990
We show that for any set Π of n points in three-dimensional space there is a set Q of 𝒪(n1/2 log3 n) points so that the Delaunay triangulation of Π ∪ Q has at most 𝒪(n3/2 log3 n) edges — even though the Delaunay triangulation of Π may have Ω(n2) edges. The main tool of our construction is the following geometric covering result: For any set Π of n points in three-dimensional space and any set S of m spheres, where each sphere passes through a distinct point pair in Π, there exists a point x, not necessarily in Π, that is enclosed by Ω(m2/n2 log3 n2/m) of the spheres in S.