Authors: Nancy M. Amato and Franco P. Preparata

Venue: International Journal of Computational Geometry & Applications
DOI: 10.1142/S021819599200010X
Link to Publication

Abstract:
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(log2 n) time using O(n) processors on a CREW PRAM. 

@article{Preparata-tp3chp-1992, 
 author = {Nancy M. Amato and Franco P. Preparata}, 
 doi = {10.1142/S021819599200010X}, 
 journal = {International Journal of Computational Geometry \& Applications}, 
 month = {June}, 
 number = {2}, 
 pages = {163--174}, 
 title = {The Parallel 3D Convex-Hull Problem Revisited}, 
 volume = {2}, 
 year = {1992} 
}