Parallel construction of quadtrees and quality triangulations

Authors
Bern, M Eppstein, D Teng, SH
Citation
M. Bern et al., Parallel construction of quadtrees and quality triangulations, INT J C GEO, 9(6), 1999, pp. 517-532
Citations number
25
Categorie Soggetti
Engineering Mathematics
Journal title
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
ISSN journal
02181959 → ACNP
Volume
9
Issue
6
Year of publication
1999
Pages
517 - 532
Database
ISI
SICI code
0218-1959(199912)9:6<517:PCOQAQ>2.0.ZU;2-U
Abstract
We describe efficient PRAM algorithms for constructing unbalanced quadtrees , balanced quadtrees, and quadtree-based finite element meshes. Our algorit hms take time O(log n) for point set input and O(bg n log Ic) time For plan ar straight-line graphs, using O(n + k log n) processors, where n measures input size and k output size.