Bowyer–Watson algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation)
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