Bowyer–Watson algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation)
Revision as of 10:52, 15 February 2023 by Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == 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/comjnl/article/24/2/167/338200")
Time Complexity
$O(nlogn)$
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