|
Abstract : |
We give fast randomized and deterministic parallel methods for constructing convex hulls in IR d, for any fixed d. Our methods are for the weakest shared-memory model, the EREW PRAM, and have optimal work bounds (with high probability for the randomized methods). In particular, we show that the convex hull of n points in IR d can be constructed in O(logn) time using O(n log n + n bd=2c work, with high probability. We also show that it can be constructed deterministically in O(log 2 n) time using O(n log n) work for d = 3 and in O(logn) time using, |
