海量数据Delaunay三角网的并行构建算法

• 作者: 张真
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: Delaunay三角网 子三角网 串行 并行 归并 复杂度 加速比
• 年，卷（期）: 2013,（4）
• 所属期刊栏目: 高性能计算
• 页码范围: 1-7
• 页数: 7页
• 分类号: TP393.027
• 字数: 6911字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2013.04.001

摘要

对并行环境下Delaunay三角网的构建进行了研究.针对海量数据处理的高效性要求,提出了一种归并构网方法.该方法根据构网数据的实际分布特点,对数据点按x坐标进行排序,并将排序后的数据按给定的阈值点数依次分配给各工作线程,构建出一系列的初始子三角网,然后逐轮对相邻的子三角网进行两两归并,直至最终归并为一个三角网.该构网方法过程中子三角网间的相关性小,易于并行处理和流水线作业.该算法既适用于单机串行、多线程和多核并发环境处理,同时也适用于集群计算模式下的分布式并行处理.实验表明,该算法的时空效率较高,最坏的串行时间复杂度为O(nlogn),一般情况下不超过O(n2).