ALCOMFT-TR-01-14

Alexandre Tiskin
Parallel convex hull computation by generalised regular sampling
Warwick. Work packages 1 and 4. February 2001.

Abstract: The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We propose the first optimal deterministic BSP algorithm for computing the convex hull of a set of points in three-dimensional Euclidean space. Our algorithm is based on known fundamental results from combinatorial geometry, concerning small-sized, efficiently constructible epsilon-nets and epsilon-approximations of a given point set. The algorithm generalises the technique of regular sampling, used previously for sorting and two-dimensional convex hull computation. The BSP cost of the algorithm is optimal only for extremely large inputs, unless the number of processors is very small. However, in future it might be possible to extend the algorithm to deal with smaller inputs.

Postscript file: ALCOMFT-TR-01-14.ps.gz (96 kb).