Slimming down by adding; selecting heavily covered points

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

In this paper we derived combinatorial point selection results for geometric objects defined by pairs of points. In a nutshell, the results say that if many pairs of a set of n points in some fixed dimension each define a geometric object of some type, then there is a point covered by many of these objects. Based on such a result for three-dimensional spheres we show that the combinatorial size of the Delaunay triangulation of a point set in space can be reduced by adding new points. We believe that from a practical point of view this is the most important result of this paper.

Original languageEnglish (US)
Title of host publicationProc Sixth Annu Symp Comput Geom
PublisherPubl by ACM
Pages116-127
Number of pages12
ISBN (Print)0897913620, 9780897913621
DOIs
StatePublished - Jan 1 1990
EventProceedings of the Sixth Annual Symposium on Computational Geometry - Berkeley, CA, USA
Duration: Jun 6 1990Jun 8 1990

Publication series

NameProc Sixth Annu Symp Comput Geom

Conference

ConferenceProceedings of the Sixth Annual Symposium on Computational Geometry
CityBerkeley, CA, USA
Period6/6/906/8/90

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Slimming down by adding; 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. (1990). Slimming down by adding; selecting heavily covered points. In Proc Sixth Annu Symp Comput Geom (pp. 116-127). (Proc Sixth Annu Symp Comput Geom). Publ by ACM. https://doi.org/10.1145/98524.98551