并行计算Voronoi图k阶邻近：矩阵迭代新方法

"这篇论文研究了Voronoi图k阶邻近关系的并行矩阵迭代算法，旨在解决传统方法在构建复杂发生元时的困难和耗时问题。论文提出了一种新的计算方法，该方法利用矩阵迭代并在刀片机上进行并行计算，通过ArcGIS软件将矢量数据转换为栅格数据，实现MPI并行环境下的Voronoi图k阶邻近计算。实验结果证明，改进的算法显著提高了计算效率，特别是在栅格Voronoi图精度较高时，加速比有明显提升。" 在空间信息科学中，Voronoi图是一种关键的数据结构，常用于空间数据模型、空间分析、空间查询等多种场景。Gold将具有公共Voronoi边的空间目标定义为相邻关系，而Kainz等人的工作进一步发展了空间目标之间的包含关系，引入了Voronoi图k阶邻近的概念。Zhao R等人提出了三种Voronoi图k阶邻近关系的生成算法：波浪法、对向法和穿越法。然而，波浪法和对向法的数据结构复杂，计算难度大；穿越法虽然计算效率高，但仅能提供近似的阶数解。李佳田提出了一种基于Voronoi图几何邻近的局部计算方法，但未充分考虑计算效率；而闫超德则利用链式邻接表来存储邻近关系，但其数据结构仍然复杂。 本文关注的是Voronoi图k阶邻近的并行计算优化。作者们首先回顾了Zhao R的算法，并在此基础上，设计了一种基于矩阵迭代的并行计算方法。这种方法选择刀片机作为硬件平台，利用ArcGIS软件将MapInfo格式的矢量数据转换为栅格数据，以便于并行处理。在MPI并行环境下，这种新方法有效地解决了传统栅格法的耗时问题，提高了Voronoi图k阶邻近的计算效率。实验结果显示，改进后的算法在保持较高精度的同时，显著缩短了运行时间，尤其是在栅格Voronoi图精度较高的情况下，加速比得到了显著提升，表明该算法在并行计算上的优越性。 这篇论文的研究对于提高空间邻近关系计算的效率和精度具有重要意义，尤其是在大规模空间数据处理和分析的背景下，这种并行矩阵迭代算法有望成为Voronoi图k阶邻近计算的一种高效解决方案。同时，它也为未来在GIS、空间推理等领域的应用提供了新的思路和技术支持。