Parallel Construction of Subdivision Hierarchies
ID
TR-87-13
Publishing date
May 1987
Abstract
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.
File(s)