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.
Import240304020342 (talk | contribs)
Set profile property.
 
(2 intermediate revisions by one other user not shown)
Property / reviewed by
 
Property / reviewed by: Plamen Yordanov Yalamov / rank
Normal 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

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
    0 references
    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

    Identifiers