Dynamic Strip Partitioning Method Oriented Parallel Computing for Construction of Delaunay Triangulation

  • 1. School of Geographic Science, Nanjing Normal University, Nanjing 210046, China;
    2. Key Laboratory of Virtual Geographic Environment, MOE, Nanjing 210046, China;
    3. Key Laboratory of Geographic Information Science of Jiangsu Province, Nanjing Normal University, Nanjing 210046, China

Received date: 2011-04-27

  Revised date: 2011-12-14

  Online published: 2012-02-24

Supported by



Data partitioning is an important step of parallel algorithm design. The load balance and efficiency of data partitioning is the precondition for improvement of parallel algorithm efficiency. For aggregated distributed point sets, the traditional Delaunay triangulation parallel algorithm can't ensure the balance and the execution's efficiency of the partitioning result. In view of the problems above, this paper we proposed a partitioning method using dynamic strips based on the idea of equally strips partitioning method in traditional Delaunay Triangulation construction and we titled it Dynamic Strip Partitioning Method. The detailed steps of this algorithm are as follows. First, the minimum bounding rectangle of the point data set should be obtained and the point set is roughly split using regular slim strips in the same direction. Then the number of points in every strip would be counted and the neighbor strips are merged into a partition region from the first strip in the sequence following a certain regulation. The boundaries of some strips should be moved dynamically if the total amount of points in these strips reached the load threshold value. In order to promote the efficiency of partitioning and reduce the boundaries movement, a rule of "move half points a time" has been used. We tested the speed-up of the Delaunay Triangulation parallel algorithm using the artificial point sets and tested the performance of the Delaunay triangulation parallel algorithm using the real test area point sets in the multi-kernel parallel computing systems. The results of the experiments showed that the method of dynamic strips partitioning can help to get high and stable speed-up of the Delaunay triangulation parallel algorithm and the data distributional pattern and size has less influence to it. Delaunay triangulation parallel algorithm based on dynamic strips partitioning method can get high efficiency and the speed-up effect is superior to the traditional method.

Cite this article

QI Lin, SHEN Jie, GUO Lishuai, ZHOU Tong . Dynamic Strip Partitioning Method Oriented Parallel Computing for Construction of Delaunay Triangulation[J]. Journal of Geo-information Science, 2012 , 14(1) : 55 -61 . DOI: 10.3724/SP.J.1047.2012.00055


[1] 汤国安,刘学军,闾国年. 数字高程模型及地学分析的原理与方法[M].北京:科学出版社,2005.

[2] 李水乡,陈斌,赵亮,等.快速Delaunay逐点插入网格生成算法[J].北京大学学报(自然科学版),2007,43(3):302-306.

[3] 艾廷华,刘耀林.保持空间分布特征的群点化简方法[J].测绘学报,2002,31(002):175-181.

[4] Yan H and Weibel R. An algorithm for point cluster generalization based on the Voronoi diagram[J]. Computers & Geosciences, 2008, 34(8): 939-954.

[5] Davy J R, Dew P M. A note on improving the performance of Delaunay triangulation[C]. // Proc. of Computer Graphics International '89, 1989.

[6] Jiang J, Zhang M, Liao X. Study of load balancing algorithms based on multiple resources[J]. Acta Electronica Sinica, 2002, 30(8):1148-1152.

[7] Cignoni P, Montani C, Perego R, et al. Parallel 3D Delaunay triangulation[C].Wiley Online Library, 1993.

[8] Chen M B, Chuang T R, Wu J J. Efficient parallel implementations of 2D Delaunay triangulation with high performance FORTRAN [J].2000.

[9] Hardwick J C. Implementation and evaluation of an efficient parallel Delaunay triangulation algorithm[C]. ACM, 1997.

[10] Wang S and Armstrong M P, A quadtree approach to domain decomposition for spatial interpolation in grid computing environments[J]. Parallel Computing, 2003,29(10): 1481-1504.

[11] 赵春宇,孟令奎,林志勇.一种面向并行空间数据库的数据划分算法研究[J].武汉大学学报:信息科学版,2006,31(11):962-965.

[12] 贾婷,魏祖宽,唐曙光,等.一种面向并行空间查询的数据划分方法[J].计算机科学,2010,37(8):198-200.

[13] 武晓波,王世新,肖春生. Delaunay 三角网的生成算法研究[J].测绘学报,1999,28(1):28-35

[14] 周侗,龙毅,汤国安,等.面向集聚分布空间数据的混合式索引方法研究[J].地理与地理信息科学,2010(001):7-10.

[15] 陈国良.并行算法的设计与分析[M].北京:高等教育出版社,1994.