De Berg; Cheong (2-Dimensional Delaunay Triangulation Delaunay Triangulation): Difference between revisions
Jump to navigation
Jump to search
(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) == 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") |
No edit summary |
||
| Line 1: | Line 1: | ||
== Time Complexity == | == Time Complexity == | ||
$O( | $O(n \log n)$ | ||
== Space Complexity == | == Space Complexity == | ||
Latest revision as of 09:44, 10 April 2023
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