Belloch (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 and which triangles to remove (see other incremental algos)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 2006 == Reference == https://web.archive.org/web/20180425231851/https://www.cs.cmu.edu/~ygu1/pape...") |
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 and which triangles to remove (see other incremental algos))
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Real RAM?
Year
2006
Reference
https://web.archive.org/web/20180425231851/https://www.cs.cmu.edu/~ygu1/paper/SPAA16/Incremental.pdf