Abstract: In view of the difficulty of vector method in building the Voronoi diagram k-order neighborhood with complex occurring elements, the problem of time-consuming and restricted accuracy with the raster method, this paper presents an iteration calculation based on the spatial objects adjacency matrix. The hardware is blade computer, MapInfo format vector data conversion for raster data by Arcgis software, and the new method implements the raster-based Voronoi diagram of k-order neighborhood in MPI parallel computing. Experiments show that MPI model significantly improves the calculation efficiency of the raster-based Voronoi diagram of k-order neighborhood. Experiments move knee point of running time back and get higher speed-up ratio, when the accuracy of raster-based Voronoi diagram is higher.

Key words: k-order neighbors, Voronoi diagram, iteration matrix, parallel computing, Message Passing Interface（MPI）

摘要： 针对Voronoi图k阶邻近矢量法构建复杂发生元困难，栅格法耗时长、精度受限等问题，提出了一种基于矩阵迭代的并行计算方法。以刀片机作为并行计算的硬件平台，采用Arcgis软件将MapInfo格式矢量数据转换为栅格数据，实现了MPI并行环境中Voronoi图k阶邻近的栅格计算新方法。实验结果表明，改进后的Voronoi图k阶邻近栅格并行算法明显地提高了计算效率，且在栅格Voronoi图精度较高时，运行时间的拐点后移，加速比提高。

关键词: k阶邻近, Voronoi图, 矩阵迭代, 并行计算, 消息传递接口（MPI）