A time-optimal delaunay refinement algorithm in two dimensions

Sariel Har-Peled, Alper Üngör

Research output: Contribution to conferencePaperpeer-review

Abstract

We propose a new refinement algorithm to generate size-optimal quality-guaranteed Delaunay triangulations in the plane. The algorithm takes O(n log n + m) time, where n is the input size and m is the output size. This is the first time-optimal Delaunay refinement algorithm.

Original languageEnglish (US)
Pages228-236
Number of pages9
DOIs
StatePublished - 2005
Event21st Annual Symposium on Computational Geometry, SCG'05 - Pisa, Italy
Duration: Jun 6 2005Jun 8 2005

Other

Other21st Annual Symposium on Computational Geometry, SCG'05
Country/TerritoryItaly
CityPisa
Period6/6/056/8/05

Keywords

  • Delaunay triangulation
  • Mesh quality
  • Mesh refinement
  • Quadtree
  • Steiner points

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'A time-optimal delaunay refinement algorithm in two dimensions'. Together they form a unique fingerprint.

Cite this