The greedy triangulation can be computed from the Delaunay triangulation in linear time (Q1969592): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
| (3 intermediate revisions by 2 users not shown) | |||
| Property / reviewed by | |||
| Property / reviewed by: Plamen Yordanov Yalamov / rank | |||
| Property / reviewed by | |||
| Property / reviewed by: Plamen Yordanov Yalamov / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| links / mardi / name | links / mardi / name | ||
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
