---
_id: '3555'
abstract:
- lang: eng
  text: A sliver is a tetrahedron whose four vertices lie close to a plane and whose
    perpendicular projection to that plane is a convex quadrilateral with no short
    edge. Slivers are both undesirable and ubiquitous in 3-dimensional Delaunay triangulations.
    Even when the point-set is well-spaced, slivers may result. This paper shows that
    such a point set permits a small perturbation whose Delaunay triangulation contains
    no slivers. It also gives deterministic algorithms that compute the perturbation
    of n points in time O(n log n) with one processor and in time O(log n) with O(n)
    processors.
article_processing_charge: No
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Xiang
  full_name: Li, Xiang
  id: 4B7E523C-F248-11E8-B48F-1D18A9856A87
  last_name: Li
- first_name: Gary
  full_name: Miller, Gary
  last_name: Miller
- first_name: Andreas
  full_name: Stathopoulos, Andreas
  last_name: Stathopoulos
- first_name: Dafna
  full_name: Talmor, Dafna
  last_name: Talmor
- first_name: Shang
  full_name: Teng, Shang
  last_name: Teng
- first_name: Alper
  full_name: Üngör, Alper
  last_name: Üngör
- first_name: Noel
  full_name: Walkington, Noel
  last_name: Walkington
citation:
  ama: 'Edelsbrunner H, Li X, Miller G, et al. Smoothing and cleaning up slivers.
    In: <i>Proceedings of the 32nd Annual ACM Symposium on Theory of Computing</i>.
    ACM; 2000:273-277. doi:<a href="https://doi.org/10.1145/335305.335338">10.1145/335305.335338</a>'
  apa: 'Edelsbrunner, H., Li, X., Miller, G., Stathopoulos, A., Talmor, D., Teng,
    S., … Walkington, N. (2000). Smoothing and cleaning up slivers. In <i>Proceedings
    of the 32nd annual ACM symposium on Theory of computing</i> (pp. 273–277). Portland,
    OR, USA: ACM. <a href="https://doi.org/10.1145/335305.335338">https://doi.org/10.1145/335305.335338</a>'
  chicago: Edelsbrunner, Herbert, Xiang Li, Gary Miller, Andreas Stathopoulos, Dafna
    Talmor, Shang Teng, Alper Üngör, and Noel Walkington. “Smoothing and Cleaning
    up Slivers.” In <i>Proceedings of the 32nd Annual ACM Symposium on Theory of Computing</i>,
    273–77. ACM, 2000. <a href="https://doi.org/10.1145/335305.335338">https://doi.org/10.1145/335305.335338</a>.
  ieee: H. Edelsbrunner <i>et al.</i>, “Smoothing and cleaning up slivers,” in <i>Proceedings
    of the 32nd annual ACM symposium on Theory of computing</i>, Portland, OR, USA,
    2000, pp. 273–277.
  ista: 'Edelsbrunner H, Li X, Miller G, Stathopoulos A, Talmor D, Teng S, Üngör A,
    Walkington N. 2000. Smoothing and cleaning up slivers. Proceedings of the 32nd
    annual ACM symposium on Theory of computing. STOC: Symposium on the Theory of
    Computing, 273–277.'
  mla: Edelsbrunner, Herbert, et al. “Smoothing and Cleaning up Slivers.” <i>Proceedings
    of the 32nd Annual ACM Symposium on Theory of Computing</i>, ACM, 2000, pp. 273–77,
    doi:<a href="https://doi.org/10.1145/335305.335338">10.1145/335305.335338</a>.
  short: H. Edelsbrunner, X. Li, G. Miller, A. Stathopoulos, D. Talmor, S. Teng, A.
    Üngör, N. Walkington, in:, Proceedings of the 32nd Annual ACM Symposium on Theory
    of Computing, ACM, 2000, pp. 273–277.
conference:
  end_date: 2000-05-23
  location: Portland, OR, USA
  name: 'STOC: Symposium on the Theory of Computing'
  start_date: 2000-05-21
date_created: 2018-12-11T12:03:56Z
date_published: 2000-06-01T00:00:00Z
date_updated: 2023-05-02T14:07:00Z
day: '01'
doi: 10.1145/335305.335338
extern: '1'
language:
- iso: eng
month: '06'
oa_version: None
page: 273 - 277
publication: Proceedings of the 32nd annual ACM symposium on Theory of computing
publication_identifier:
  isbn:
  - '9781581131840'
publication_status: published
publisher: ACM
publist_id: '2830'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Smoothing and cleaning up slivers
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2000'
...