Preparata and Hong (2-dimensional; 3-dimensional Convex Hull)

From Algorithm Wiki

Revision as of 08:34, 10 April 2023 by Admin (talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to navigation Jump to search

Time Complexity

$O(nlogn)$

Space Complexity

$O(n)$? words

(Divide and conquer can be done in linear space total as space can be reused after conquer steps)

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Real RAM

Year

1977

Reference

https://dl.acm.org/citation.cfm?id=359430

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Preparata_and_Hong_(2-dimensional;_3-dimensional_Convex_Hull)&oldid=47342"