The greedy triangulation can be computed from the Delaunay triangulation in linear time (Q1969592): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 16:39, 1 February 2024
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
