Selecting heavily covered points

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, John E. Hershberger, Raimund Seidel, Micha Sharir

Research output: Contribution to journalArticle

10 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1138-1151
Number of pages14
JournalSIAM Journal on Computing
Volume23
Issue number6
DOIs
StatePublished - Jan 1 1994

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Selecting heavily covered points'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., Edelsbrunner, H., Guibas, L. J., Hershberger, J. E., Seidel, R., & Sharir, M. (1994). Selecting heavily covered points. SIAM Journal on Computing, 23(6), 1138-1151. https://doi.org/10.1137/S0097539790179919