Selecting heavily covered points Journal Article


Author(s): Chazelle, Bernard; Edelsbrunner, Herbert; Guibas, Leonidas J; Hershberger, John E; Seidel, Raimund; Sharir, Micha
Article Title: Selecting heavily covered points
Affiliation
Abstract: A collection of geometric selection lemmas is proved, such as the following: 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 Ω(m2/(n2 log6 n2/m)) of the spheres in S. Similar results apply in arbitrary fixed dimensions, and for geometric bodies other than spheres. The results have applications in reducing the size of geometric structures, such as three-dimensional Delaunay triangulations and Gabriel graphs, by adding extra points to their defining sets.
Journal Title: SIAM Journal on Computing
Volume: 23
Issue 6
ISSN: 0097-5397
Publisher: SIAM  
Date Published: 1994-12-01
Start Page: 1138
End Page: 1151
DOI: 10.1137/S0097539790179919
Open access: no
IST Austria Authors
Related IST Austria Work