Slimming down by adding; selecting heavily covered points

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

doi:10.1145/98524.98551

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 proceeding › Conference 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 language	English (US)
Title of host publication	Proc Sixth Annu Symp Comput Geom
Publisher	Publ by ACM
Pages	116-127
Number of pages	12
ISBN (Print)	0897913620, 9780897913621
DOIs	https://doi.org/10.1145/98524.98551
State	Published - Jan 1 1990
Event	Proceedings of the Sixth Annual Symposium on Computational Geometry - Berkeley, CA, USA Duration: Jun 6 1990 → Jun 8 1990

Publication series

Name	Proc Sixth Annu Symp Comput Geom

Conference

Conference	Proceedings of the Sixth Annual Symposium on Computational Geometry
City	Berkeley, CA, USA
Period	6/6/90 → 6/8/90

All Science Journal Classification (ASJC) codes

Engineering(all)

Access to Document

10.1145/98524.98551

Cite this

@inproceedings{a10e2fad77fe4ae6b28c6c3826507216,

title = "Slimming down by adding; selecting heavily covered points",

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.",

author = "Bernard Chazelle and Herbert Edelsbrunner and Guibas, {Leonidas J.} and Hershberger, {John E.} and Raimund Seidel and Micha Sharir",

year = "1990",

month = jan,

day = "1",

doi = "10.1145/98524.98551",

language = "English (US)",

isbn = "0897913620",

series = "Proc Sixth Annu Symp Comput Geom",

publisher = "Publ by ACM",

pages = "116--127",

booktitle = "Proc Sixth Annu Symp Comput Geom",

note = "Proceedings of the Sixth Annual Symposium on Computational Geometry ; Conference date: 06-06-1990 Through 08-06-1990",

}

Chazelle, B, Edelsbrunner, H, Guibas, LJ, Hershberger, JE, Seidel, R & Sharir, M 1990, Slimming down by adding; selecting heavily covered points. in Proc Sixth Annu Symp Comput Geom. Proc Sixth Annu Symp Comput Geom, Publ by ACM, pp. 116-127, Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, 6/6/90. https://doi.org/10.1145/98524.98551

TY - GEN

T1 - Slimming down by adding; selecting heavily covered points

AU - Chazelle, Bernard

AU - Edelsbrunner, Herbert

AU - Guibas, Leonidas J.

AU - Hershberger, John E.

AU - Seidel, Raimund

AU - Sharir, Micha

PY - 1990/1/1

Y1 - 1990/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0025054886&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025054886&partnerID=8YFLogxK

U2 - 10.1145/98524.98551

DO - 10.1145/98524.98551

M3 - Conference contribution

AN - SCOPUS:0025054886

SN - 0897913620

SN - 9780897913621

T3 - Proc Sixth Annu Symp Comput Geom

SP - 116

EP - 127

BT - Proc Sixth Annu Symp Comput Geom

PB - Publ by ACM

T2 - Proceedings of the Sixth Annual Symposium on Computational Geometry

Y2 - 6 June 1990 through 8 June 1990

ER -

Slimming down by adding; selecting heavily covered points

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this