Parallel Construction of Quadtrees and Quality Triangulations.

We describe efficient PRAM algorithms for constructing unbalanced quadtrees, balanced quadtrees, and quadtree-based finite element meshes. Our algorithms take time O(log n) for point set input and O(log n log k) time for planar straight-line graphs, using O(n+k/log n) processors, where n measures input size and k output size. [ABSTRACT FROM AUTHOR]