Parallel divide-and-conquer scheme for 2D Delaunay triangulation

author: Min-Bin Chen, Tyng-Ruey Chuang and Jan-Jan Wu
publication date: October 2006
cite this with: Min-Bin Chen, Tyng-Ruey Chuang and Jan-Jan Wu. Parallel divide-and-conquer scheme for 2D Delaunay triangulation. Concurrency and Computation: Practice and Experience, 18(12):1595-1612. October 2006.
link this with: http://tsm.iis.sinica.edu.tw/papers/ccpe06/
copyright: all rights reserved
category: others
tag:
full paper: pdf

Abstract

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.

 
papers:ccpe06:home Last modified: 2007/10/19 16:43