Technical Reports

The ICICS/CS Reading Room

UBC CS TR-87-13 Summary

Parallel Construction of Subdivision Hierarchies, May 1987 Norm Dadoun and David G. Kirkpatrick

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.

If you have any questions or comments regarding this page please send mail to