SELECTING HEAVILY COVERED POINTS

A collection of geometric selection lemmas is proved, such as the foll owing: For any set P of n points in three-dimensional space and any se t S of m spheres, where each sphere passes through a distinct paint pa ir in P, there exists a point x, not necessarily in P, that is enclose d by Omega(m(2)/(n(2) log(6) n(2)/m)) of the spheres in S. Similar res ults apply in arbitrary fixed dimensions, and for geometric bodies oth er than spheres. The results have applications in reducing the size of geometric structures. such as three-dimensional Delaunay triangulatio ns and Gabriel graphs, by adding extra points to their defining sets.