Premium
Parallel divide‐and‐conquer scheme for 2D Delaunay triangulation
Author(s) -
Chen MinBin,
Chuang TyngRuey,
Wu JanJan
Publication year - 2006
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.1007
Subject(s) - delaunay triangulation , divide and conquer algorithms , computer science , scheme (mathematics) , bowyer–watson algorithm , fortran , triangulation , parallel computing , block (permutation group theory) , parallel algorithm , ibm , node (physics) , algorithm , code (set theory) , distributed memory , mathematics , combinatorics , shared memory , geometry , programming language , mathematical analysis , materials science , structural engineering , set (abstract data type) , engineering , nanotechnology
This work describes a parallel divide‐and‐conquer Delaunay triangulation scheme. This algorithm finds the affected zone, which covers the triangulation and may be modified when two sub‐block triangulations are merged. Finding the affected zone can reduce the amount of data required to be transmitted between processors. The time complexity of the divide‐and‐conquer scheme remains O ( n log n ), and the affected region can be located in O ( n ) time steps, where n denotes the number of points. The code was implemented with C, FORTRAN and MPI, making it portable to many computer systems. Experimental results on an IBM SP2 show that a parallel efficiency of 44–95% for general distributions can be attained on a 16‐node distributed memory system. Copyright © 2006 John Wiley & Sons, Ltd.