Miller; Stout (2-dimensional Convex Hull)
Jump to navigation
Jump to search
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