1999/12/01 by Marshall Bern, David Eppstein, Shang‐Hua Teng · 2 citations
Computer Science · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Complexity and Algorithms in Graphs
paper · doi:10.1142/s0218195999000303
openalex publication_date 1999/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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.