题目：基于多核CPU的平面Voronoi图并行生成算法研究

Voronoi图是计算几何当中相当重要的一部分，并且在很多领域当中有重要的应用。由于Voronoi图具有最近性、邻接性等众多性质和比较系统的理论体系，如今已经在图形学、机械工程、地理信息系统、虚拟现实、机器人路径规划、图像处理、CAD等领域得到广泛应用，也是解决距离计算、碰撞检测、路径规划等计算几何其它问题的有效工具。鉴于它有如此广泛的应用领域和在各个方面的重要应用，研究Voronoi图的生成算法是很有理论和实际意义的。
目前，生成Voronoi图的方法有两种：矢量方法和栅格方法，矢量方法生成Voronoi图针对离散点而言是很有效的，而对于线、面等复杂的空间目标而言，算法和数据结构都非常复杂，实现起来困难很大，优点是可得到较精确的Voronoi图；栅格法生成Voronoi图相对简单一些，尤其是对于较复杂的空间目标，但是栅格数量多，生成效率相对较低，在精度上存在一定的误差。针对这些情况，本文处理的数据是实际地图数据，空间目标比较复杂，所以采用栅格方法来生成Voronoi图.
由于解决栅格Voronoi图生成算法的数据量较大，为了提高计算效率，将并行思想运用于Voronoi图生成算法中。然而多核平台的应用在这一领域尚未展开。因此，本文开展对Voronoi图的生成进行多线程并行优化，使应用程序性能大为提高。并在多核平台上进行了验证，从而得到比较高效的Voronoi图的生成算法，证明了多核平台和并行计算理论的优越性。
本文所做工作总结如下：
（1）在前人的工作基础之上，运用数学形态学中的膨胀算子，生成栅格Voronoi图，并将此算法运用到实际的地图数据上面。生成了实际地图数据的栅格Voronoi图。这在一部分当中，本文从以下四个方面进行考虑：①生长元为点状目标；②生长元为线状目标；③生长元为面状目标；④生长元为点、线、面的复合目标。
（2）在多核平台下结合并行计算理论，成功地对Voronoi图的栅格算法进行了多线程并行优化，有效地提高了效率。达到了研究目的。
（3）论文最后将Voronoi图应用到城市公共设施选址分析和优化中，对西安市的城市学校和公园的布局进行了分析，并提出了一些较合理的建议。