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

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）