Miller; Stout (2-dimensional Convex Hull): Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Time Complexity == $O(logn)$ time using $O(n)$ processors == Space Complexity == $O(n)$ total? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM, possibly others (see paper) == Year == 1988 == Reference == https://cse.buffalo.edu/faculty/miller/Papers/IEEETC88a.pdf") |
No edit summary |
||
| Line 8: | Line 8: | ||
$O(n)$ total? words | $O(n)$ total? words | ||
() | (Divide and conquer can be done in linear space total as space can be reused after conquer steps) | ||
== Description == | == Description == | ||
Latest revision as of 09:34, 10 April 2023
Time Complexity
$O(logn)$ time using $O(n)$ processors
Space Complexity
$O(n)$ total? 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
EREW PRAM, possibly others (see paper)
Year
1988