题目：Voronoi图k阶邻近并行算法研究及其应用

空间邻近关系是一类重要的空间关系，它一般是指两个空间对象之间直接相邻的一种空间关系，在这两个空间目标之间不存在其他空间对象。任何空间建模系统必须含有邻近关系的识别，Voronoi图和Delaunay 三角网是表示空间邻近关系的两种较好模型。空间邻近关系广泛应用于自然地表的内插、空间邻近查询以及地表特征线提取等方面。
空间邻近问题运用Voronoi图辅助选择k阶邻近，不仅可以避免选择过程地反复进行，减少搜索范围，而且更接近于人类的认知方式，从而可提高效率与准确度。Voronoi图栅格法较容易处理各种复杂空间目标，本文在栅格模式下讨论Voronoi图k阶邻近生成算法，但生成的Voronoi图精度取决于栅格单元的大小。为了提高生成的Voronoi图精度，主要通过细分栅格单元的大小。然而栅格单元越小，计算量就会不断增加，因此采用并行计算。考虑到Voronoi图生成的过程需要数据通信及Voronoi图k阶邻近生成算法中对数据的广播、收集及规约操作，采取消息传递的编程模式。
本文对Voronoi图k阶邻近生成算法进行了深入的探讨和研究，主要工作包括：
(1)分析了Zhao R提出的波浪法、对向法和穿越法。波浪法从给定的目标开始向其周围依次搜索该目标的所有指定阶数的邻近目标；对向法给定两个空间目标，求解两个空间目标的邻近阶数，可以分别从两个空间目标开始向其周围依次展开搜索，直到两个的目标邻近目标相遇为止。前两种算法的计算难度大、数据结构较为复杂。穿越法的数据结构简单、计算效率高，但求得的阶数为近似解。本文结合关系数据模型提出了一种基于矩阵迭代的算法，Voronoi图k阶邻近矩阵迭代算法的优势：①空间目标的k阶邻近关系利用矩阵迭代生成，减少重复计算；②由于栅格Voronoi图的数据量大，精度的提高依赖于栅格单元的细分，该算法适合栅格Voronoi图大数据集的并行化；利用矩阵存储Voronoi图k阶邻近关系，有利于对数据集的组通信（分块、广播、收集及规约等）操作的实现。
(2)考虑到Voronoi图k阶邻近的生成过程需要通信数据，设计实现了基于消息传递的Voronoi图k阶邻近并行生成算法。基于矩阵迭代的Voronoi图k阶邻近算法的计算效率在并行编程模式下有所提高：多进程的优势随着栅格单元的细分、栅格分辨率的提高愈发凸显，Voronoi图精度提高的同时MPI并行时间的拐点后移，加速比有所提高。     
(3)公共服务设施合理化布局是当前我国统筹城乡协调发展，构建社会主义和谐社会的重要课题。运用ArcGis软件对地图数据的样本进行预处理——矢栅转换。本文将Voronoi图k阶邻近应用在医疗急救系统和学校布局选址，分别从人们出行选择的合理性和设施选址优化两个角度给出了一些建议。