计算几何（Computational Geometry）是一门面向实际应用的计算科学，主要涉及几何问题算法的分析和设计，具有重要的理论价值，在计算机科学领域尤其是计算机图形学以及3D游戏、3D动画中有广泛的应用。Voronoi图是计算几何研究领域中的一个重要分支，具有良好的空间近邻性质，控制范围性质，最大空圆性质。通过Voronoi图可以快速得到凸壳和Delaunay三角剖分等其他重要几何结构。Voronoi图已经被应用到地理信息系统（GIS），图形图像学，生物医药工程，建筑学，机器人运动，路径规划，模式识别，聚类分析等领域中。高维Voronoi图的生成算法的实现和分析较为复杂，目前针对高维Voronoi图的生成算法和应用领域的研究较少。本文主要针对高维Voronoi图的随机增量生成算法，在Watson和Bowyer的算法基础上改进了初始边界凸壳的构造，单形的定位策略，并利用了Facet辅助结构，利用空间换时间的方法，加快在更新过程中单形邻居关系的维护，进而加快随机增量算法的执行效率。实验结果表明，本文中提出的改进的高维Voronoi图随机增量算法，相比于Bowyer算法，在使用更多辅助存储空间的基础上，执行效率上提高了近十倍左右。根据高维Voronoi图的性质，本文将高维Voronoi图应用在高维数据集的聚类分析和高维空间路径规划这两个领域中，并且针对每个应用问题给出了具体的分析方法和实现步骤。