---
_id: '4078'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
author:
- first_name: Bernard
  full_name: Chazelle, Bernard
  last_name: Chazelle
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: John
  full_name: Hershberger, John
  last_name: Hershberger
- first_name: Raimund
  full_name: Seidel, Raimund
  last_name: Seidel
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: 'Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. Slimming
    down by adding; selecting heavily covered points. In: <i>Proceedings of the 6th
    Annual Symposium on Computational Geometry</i>. ACM; 1990:116-127. doi:<a href="https://doi.org/10.1145/98524.98551">10.1145/98524.98551</a>'
  apa: 'Chazelle, B., Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., &#38;
    Sharir, M. (1990). Slimming down by adding; selecting heavily covered points.
    In <i>Proceedings of the 6th annual symposium on computational geometry</i> (pp.
    116–127). Berkley, CA, United States: ACM. <a href="https://doi.org/10.1145/98524.98551">https://doi.org/10.1145/98524.98551</a>'
  chicago: Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, John Hershberger,
    Raimund Seidel, and Micha Sharir. “Slimming down by Adding; Selecting Heavily
    Covered Points.” In <i>Proceedings of the 6th Annual Symposium on Computational
    Geometry</i>, 116–27. ACM, 1990. <a href="https://doi.org/10.1145/98524.98551">https://doi.org/10.1145/98524.98551</a>.
  ieee: B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, and M.
    Sharir, “Slimming down by adding; selecting heavily covered points,” in <i>Proceedings
    of the 6th annual symposium on computational geometry</i>, Berkley, CA, United
    States, 1990, pp. 116–127.
  ista: 'Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M.
    1990. Slimming down by adding; selecting heavily covered points. Proceedings of
    the 6th annual symposium on computational geometry. SCG: Symposium on Computational
    Geometry, 116–127.'
  mla: Chazelle, Bernard, et al. “Slimming down by Adding; Selecting Heavily Covered
    Points.” <i>Proceedings of the 6th Annual Symposium on Computational Geometry</i>,
    ACM, 1990, pp. 116–27, doi:<a href="https://doi.org/10.1145/98524.98551">10.1145/98524.98551</a>.
  short: B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir,
    in:, Proceedings of the 6th Annual Symposium on Computational Geometry, ACM, 1990,
    pp. 116–127.
conference:
  end_date: 1990-06-09
  location: Berkley, CA, United States
  name: 'SCG: Symposium on Computational Geometry'
  start_date: 1990-06-07
date_created: 2018-12-11T12:06:48Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-17T10:09:54Z
day: '01'
doi: 10.1145/98524.98551
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/98524.98551
month: '01'
oa_version: None
page: 116 - 127
publication: Proceedings of the 6th annual symposium on computational geometry
publication_identifier:
  isbn:
  - 978-0-89791-362-1
publication_status: published
publisher: ACM
publist_id: '2046'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Slimming down by adding; selecting heavily covered points
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...