The greedy triangulation can be computed from the Delaunay triangulation in linear time (Q1969592)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The greedy triangulation can be computed from the Delaunay triangulation in linear time |
scientific article |
Statements
The greedy triangulation can be computed from the Delaunay triangulation in linear time (English)
0 references
22 October 2000
0 references
The Delaunay triangulation can be produced in \(O(n\log n)\) worst-case time, and often even faster, by several practical algorithms. The authors show that for any planar point set \(S\), if the Delaunay triangulation of \(S\) is given, then the greedy triangulation of \(S\) can be computed in linear worst-case time.
0 references
greedy triangulation
0 references
Delaunay triangulation
0 references
linear worst-case time
0 references
Voronoi diagram
0 references
