# The ICICS/CS Reading Room

## UBC CS TR-87-13 Summary

- No on-line copy of this technical report is available.

- 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
help@cs.ubc.ca.