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 language | English (US) |
|---|---|
| Pages | 228-236 |
| Number of pages | 9 |
| DOIs | |
| State | Published - 2005 |
| Event | 21st Annual Symposium on Computational Geometry, SCG'05 - Pisa, Italy Duration: Jun 6 2005 → Jun 8 2005 |
Other
| Other | 21st Annual Symposium on Computational Geometry, SCG'05 |
|---|---|
| Country/Territory | Italy |
| City | Pisa |
| Period | 6/6/05 → 6/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
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS