Belloch (2-Dimensional Delaunay Triangulation Delaunay Triangulation)

From Algorithm Wiki
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 (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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/paper/SPAA16/Incremental.pdf

Retrieved from "https://algorithm-wiki-csail-mit-edu.ezproxy.canberra.edu.au/w/index.php?title=Belloch_(2-Dimensional_Delaunay_Triangulation_Delaunay_Triangulation)&oldid=44840"