The greedy triangulation can be computed from the Delaunay triangulation in linear time (Q1969592): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Latest revision as of 05:23, 5 March 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
