Parallel Construction of Subdivision Hierarchies

Norm Dadoun and David G. Kirkpatrick
Publishing date
May 1987

A direct, simple and general parallel algorithm is described for the preprocessing of a planar subdivision for fast (sequential) search. In essence, the hierarchical subdivision search structure described by Kirkpatrick [K] is constructed in parallel. The method relies on an efficient parallel algorithm for constructing large independent sets in planar graphs. This is accomplished by a simple reduction to the same problem for lists.

Applications to the manipulation of convex polyhedra are described including an \( O(\log^{2}n \log^{*}n) \) parallel time algorithm for constructing the convex hull of $n$ points in $R^{3}$ and an \( O( \log n \log^{*}n) \) parallel time algorithm for detecting the separation of convex polyhedra.