THE PARALLEL 3D CONVEX HULL PROBLEM REVISITED
Nancy M. Amato, Franco P. Preparata · International Journal of Computational Geometry & Applications · 1992
In this paper we prove the correctness of a “local” criterion for computing the convex hull of the union ( “merging”) of two disjoint convex polyhedra. This criterion is structural. Therefore it can be algorithmically tested in several ways, not necessarily involving the determination of support (tangent) planes; indeed, it can be implemented by just testing for the intersection of certain planes and lines with convex polytopes. This criterion is amenable to parallel implementation and leads to a provably correct algorithm that computes the convex hull of any n points in three-dimensional space in O( log 2 n) time using O(n) processors on a CREW PRAM.