Voronoi图是计算几何中常用而又重要的几何结构,它有很强的实用价值.本文首先介绍了平面点集上的Voronoi图和Voronoi图的一些生成方法,着重介绍了平面扫描生成算法的主要步骤.之后,提出与Voronoi图相对偶的三角剖分问题.利用Voronoi图良好的特性,结合实际应用背景,本文根据空域中航路点的自然分布,利用计算几何的思想建立其Voronoi图,以此为依托,在文[10]的研究基础上,对于空域扇区优化划分问题进行了研究,将文[10]中投影平面上的空域划分,拓展到三维空域中,并以工作负荷均衡为优化原则,对空域中的有限元进行优化组合,该项研究对于提高空域容量和保障飞行安全具有重要作用.进一步,本文将Voronoi图的概念拓展到了一般的参数曲面,即曲面上的Voronoi图的生成,曲面上两点之间的距离由两点之间的测地距离所定义,由此得到了在曲面上用分治法构造Voronoi图的一般方法,且该方法与曲面如何参数化无关.本文用该方法,在球面上进行了Voronoi图的划分.许多限制在曲面上的曲面构造方法,基本上是基于对曲面的三角化的插值方法,三角化过程相当复杂,计算代价非常大,对所用插值方法影响非常大,而由在一般参数曲面上所得的Voronoi图很方便即可求得其对应的三角网格,本文对于球面Voronoi图求得其上相应的对偶三角网格,在此基础上,对球面上的曲面插值问题进行了研究.