voronoi_construction

Voronoi图是一种在平面或更高维空间中将一组点分割成多个区域的几何结构。每个区域都有一个称为Voronoi顶点的点，该点是其所有相邻区域的最近点。Voronoi图的构建过程通常开始于一组离散的点，然后通过迭代地将每个点与其最近的Voronoi顶点连接起来，直到所有的Voronoi边都已经被确定。这个过程可以通过许多不同的算法来实现，包括Fortune's algorithm、Sweep line algorithm和Divide and conquer algorithm等。Voronoi图在许多领域都有应用，包括地理信息系统、计算机图形学、机器人学和运筹学等。