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