Parallel construction of subdivision hierarchies

摘要

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 (SIAM J. Comput.12, No. 1 (1983), 28–35) 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(log2 n log∗ n) parallel time algorithm for constructing the convex hull of n points in R3 and an O(log n log∗ n) parallel time algorithm for detecting the separation of convex polyhedra.