PARALLEL CONSTRUCTION OF QUADTREES AND QUALITY TRIANGULATIONS
Marshall W. Bern, David Eppstein, Shang‐Hua Teng · International Journal of Computational Geometry & Applications · 1999
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.