● 摘要
Voronoi图是一种按距离进行空间划分的基础数据结构，反应的是一种同等对待所有生成元的理想状态，但在实际应用中，生成元的影响范围受各种因素的影响，因此需在普通Voronoi图的基础上，对生成元赋予权重，构成加权Voronoi图。
加权Voronoi的生成方法主要分为矢量法和栅格法。矢量法计算精度高，但数据结构复杂，处理线状和面状生成元较困难。当面临海量复杂的实际地图数据时，矢量方法不能很好地满足现实需求。栅格法虽然生成精度受到限制，但可以进行任意生成元的构建，能较好地处理复杂空间实体。另外，实际地图数据呈现大规模、海量化趋势，串行的栅格方法计算效率不高，并行化处理为其提供了一个有效的改进和优化方案。
传统的Voronoi图并行方法通常是基于MPI、OpenMP、GPU等并行环境，虽然能够高效并行地生成Voronoi图，但受到底层配置和实现细节等因素的限制，而MapReduce因其高可靠性、高效率且能部署于廉价硬件设备等优点，简化了分布式程序设计，提高了计算性能，能够较好地解决大规模数据的Voronoi图计算问题。
因此，本文对加权Voronoi图在MapReduce模型下的并行生成算法及其应用进行了深入研究，主要工作包括：
（1）对加权Voronoi图的基本概念、应用、生成算法等相关理论进行了阐述，探讨了Hadoop平台的相关技术，为后续研究提供了理论指导。
（2）针对传统加权Voronoi图栅格生成算法计算效率不高的缺陷，提出了一种基于MapReduce模型的加权Voronoi图并行算法，并在Hadoop集群上对算法的加速比和可扩展性进行了实验分析。
（3）本文将加权Voronoi图应用于超市推荐和污水处理厂规划布局问题。针对超市推荐问题，以大众点评网的超市用户评分数据为依据，给出了一种综合多种用户评价指标的权重确定方法，应用加权Voronoi图，为用户推荐最优的大型综合性超市。针对污水处理厂规划布局问题，通过将断裂点模型中的“规模”参数引入到加权Voronoi图中，构建了基于加权Voronoi图的污水处理厂的责任区域界定模型，为污水处理厂的规划布局提供参考。