给定一个 Voronoi 图的生成点，计算其顶点 EN

计算平面中的Voronoi区域相当于计算n半平面的交点-由点p_i和每个其他点p_j之间的平分线定义的半平面。但是，此问题等价于(通过对偶)计算平面中n点的凸包(请参见离散和计算几何手册中的Chapter 30.5 on Arrangements )。计算\Omega(n log n)的平面has a known lower bound中一组点的凸包。

计算Delaunay三角剖分只需要O(n log n)时间。因此，像@matt-timmermans和@yves-daoust建议的那样，将输入预处理到Delaunay三角剖分中，没有实际的开销，可能是大多数应用程序的最佳选择。

一旦计算了Delaunay三角剖分，每个查询(区域边界的构建)只需要O(1 + k)时间，其中k是输出大小，即Voronoi区域边界上的顶点/边的数量。请注意，k本身可以是\Omega(n)，例如，如果n-1点或多或少地放置在一个圆上，并且p_i靠近其中心。

虽然最坏情况下的算法是\Omega(n log n)，因此并不比计算Delaunay三角剖分好，但也有一种输出敏感算法可以采用O(n*k) (取决于输出Voronoi区域的大小)。

在Voronoi区域的边界上找到单个顶点等同于线性规划问题的结果(参见Computational Geometry: Algorithms and Applications的第4章)。

特别是，Megiddo的算法或其随机化版本(上面这本书的第4.4章)在O(n)线性时间内运行。一旦找到第一个顶点及其两条生成线，就可以通过将剩余的线与生成线相交来找到下一个顶点。最近的交点是下一个Voronoi顶点，然后最近的交线成为下一条要与之相交的直线。当再次到达第一个顶点时，该过程将终止。总而言之，每次迭代都需要O(n)，并且有k迭代，所以这个算法总共需要O(n*k)。