从曲面的三维采样点集恢复出曲面的几何模型称之为曲面重建。曲面重建是许多研究领域如逆向工程,医学图像可视化中的重要问题,因此,曲面重建问题被广泛地研究,产生了许多曲面重建算法。基于Voronoi图的曲面重建算法是其中一类使用较广泛的重建算法,该算法主要是通过构造采样点集的Voronoi图并对其进行三角剖分来重建曲面。但随着激光测距扫描等测量设备的快速发展,人们得到的采样点集呈海量的趋势,致使Voronoi图的构造速度较慢,进而也降低了曲面重建的速度。因此,为了最终提高此类曲面重建算法的速度,本文从并行角度出发,主要对其中Voronoi图的并行构造算法进行了研究。首先,系统地分析了平面求交法、增量法、平面扫描法和分治法这四种串行构造Voronoi图的算法的并行性。从可否并行化、并行度、粒度和存储类型四个方面对这四种算法的并行性进行了综合对比。并且对其中分治法的并行性进行了挖掘,对分治法中的合并算法进行了扩展。其次,基于以上对串行算法的并行性分析,结合目前双核系统的广泛使用性。以平面扫描法为基础,提出了一种适用于双核系统的Voronoi图的并行算法。该算法采用并行双向扫描的思想,结合本文提出的一种组合结构,使其既能提高Voronoi图的构造速度,又能保持双核负载平衡。最后,结合机群系统的广泛使用性,以分治法为基础,提出了一种适用于机群系统的Voronoi图的并行算法。针对该并行算法中合并过程的复杂性,提出了最短等待合并策略并设计了一种节点状态双向链表来维持算法的正确执行并实现了动态合并。