Bowyer–Watson algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation)

From Algorithm Wiki

Jump to navigation Jump to search

Time Complexity

$O(n \log n)$

Space Complexity

$O(n)$ words

(Keep track of triangles in current triangulation, based on which points have been added so far and which triangles to remove)

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Real RAM?

Year

1981

Reference

https://academic-oup-com.ezproxy.canberra.edu.au/comjnl/article/24/2/167/338200

Retrieved from "https://algorithm-wiki-csail-mit-edu.ezproxy.canberra.edu.au/w/index.php?title=Bowyer–Watson_algorithm_(2-Dimensional_Delaunay_Triangulation_Delaunay_Triangulation)&oldid=47436"