Voronoi Diagrams — A Survey of a Fundamental Geometric Data Stru...

Voronoi图是一种在计算几何领域内非常基础且重要的数据结构。Aurenhammmer在1991年发表的这篇综述，详细总结了Voronoi图的历史、定义、性质、算法、扩展和应用。这篇文章强调了Voronoi图在计算机科学内外的广泛领域中的重要性和实用性，对Voronoi图的数学和算法性质进行了统一阐述，并提供了首个全面的关于Voronoi图和相关结构的文献目录。 Voronoi图的研究始于19世纪，由俄国数学家Georgy Voronoy提出，它是一种对平面或空间中一组离散点进行分割的方法。每个点都被赋予一个区域，区域内的点到该点的距离比到其他任何点的距离都近。在平面情况下，每个点的区域是由平面上距离该点最近的其他点所界定的多边形，被称为Voronoi多边形。这些多边形组合起来就构成了Voronoi图。 Voronoi图在多个领域有着广泛的应用。例如，在城市规划中，Voronoi图可以用来确定服务设施的最佳位置，使得居民到达设施的距离最小化。在自然领域，例如在植物叶脉或动物皮肤图案的形成中，Voronoi图可以用来模拟生长过程。在计算机科学领域，Voronoi图被应用于图形学、机器人学、模式识别、地理信息系统等多种场景中。 Voronoi图的数学性质和算法处理是其研究的重要部分。数学上，Voronoi图与凸包、最短路径、点集划分等概念紧密相关。算法方面，构建Voronoi图有多种方法，包括分而治之、平面扫描、随机插入等。其中，分而治之是一种将问题规模不断缩小的策略，直至问题简化到可以直接解决的程度。平面扫描方法则是以一个不断移动的线（或平面）作为工具，来逐步构建Voronoi图。 Voronoi图的扩展在很多情况下也非常重要。比如，加权Voronoi图是每个点赋予权重，其区域的形成基于距离与权重的组合。高维Voronoi图则是对于更高维度空间点集的推广。而更高嵌入、超平面安排等概念扩展了Voronoi图的理论边界，为解决更复杂的问题提供了基础。 在计算机图形学和计算几何中，Voronoi图与其他的几何结构和算法有着密切的联系。例如，它与三角剖分有着天然的联系，因为可以通过Voronoi图的对偶图来生成Delaunay三角剖分。此外，Voronoi图也与最小生成树、k-集合等概念关联。运动规划中的路径查找常常利用Voronoi图来简化搜索空间。邻近搜索、对象建模、随机插入等方法也与Voronoi图紧密相关。 Voronoi图作为一种基础的几何数据结构，在理论研究与实际应用中都显示出其核心的地位。它不仅在计算几何领域有深刻的影响，还扩展到其他诸多领域，如机器人学、计算机图形学、模式识别等。Aurenhammmer的综述为Voronoi图的研究者和应用者提供了宝贵的资源，为后续的研究和应用打下了坚实的基础。