De Berg; Cheong (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)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Real RAM?
Year
2008
Reference
https://web.archive.org/web/20091028054315/http://www.cs.uu.nl/geobook/interpolation.pdf