Parallel construction of quadtrees and quality triangulations

被引：45

作者：

Bern, M

Eppstein, D

Teng, SH

机构：

[1] Xerox Palo Alto Res Ctr, Palo Alto, CA 94304 USA

[2] Univ Calif Irvine, Dept Informat & Comp Sci, Irvine, CA 92717 USA

[3] MIT, Dept Math, Cambridge, MA 02139 USA

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 1999年 / 9卷 / 06期

关键词：

quadtree; mesh generation; nonobtuse triangulation; fair split tree; parallel algorithms; PRAM model;

D O I：

10.1142/S0218195999000303

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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(bg n log Ic) time For planar straight-line graphs, using O(n + k log n) processors, where n measures input size and k output size.

引用

页码：517 / 532

页数：16

共 25 条

[1]

[Anonymous], TR89983 CORN U DEP C

[2] Nearly linear time approximation schemes for euclidean TSP and other geometric problems [J].