The greedy triangulation can be computed from the Delaunay triangulation in linear time (Q1969592): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q586759 |
||
| Property / reviewed by | |||
| Property / reviewed by: Plamen Yordanov Yalamov / rank | |||
Revision as of 08:53, 16 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
