构建个点的 Voronoï 图已经需要时间。我假设您要计算的是 Voronoï 图与多边形的交集。一种计算时间的方法（其中是多边形和 Voronoï 图之间的交叉点数）是首先计算 Voronoï 图，然后通过任何足够快的算法（例如使用 Bentley-Ottmann 核心的扫描线算法）计算与多边形的交集。$n$$O(n \log n)$$O((n+p+k) \log(n+p))$$k$

对于一般多边形，我们有。对于凸多边形，我们有，你可能假设，所以。这比更糟糕，但这仅仅是因为我们忽略了构建 Voronoï 图所需$k=O(np)$$k=O(n)$$p<n$$O((n+p+k) \log(n+p))=O(n\log n)$$O(n\log k)$$O(n \log n)$

（我知道使 Bentley-Ottmann 数值稳健具有挑战性，并且大多数可用的稳健实现都使用基于多精度算术的“精确谓词”。但即使这个答案可能不是最实用的，它也可以回答您关于计算的问题手头任务的复杂性。）

我建议使用我最近发表的一篇论文中描述的方法：http: //people.seas.harvard.edu/~nbonneel/vorpaline.pdf

这个想法很简单，如下所示：
从多边形开始，目标是使用 Sutherland-Hodgman 多边形裁剪算法用每个种子定义的中介平面切割它。对于每个种子，这可以有效地并行完成。

给定一组个点，假设您要计算种子的 Voronoi 单元。首先，通过增加到的距离对所有进行排序 （对于当前种子，这是使用 kd-tree您通过段的中介平面剪裁多边形并存储从到最远交点当给定和之间的距离大于$n$$\{P_i\}$$P_k$$\{P_i\}$$P_k$$O(\log(n))$$[P_k, P_i]$$D$$P_k$$i$$P_k$$P_i$$2\,D$，您可以停下来，这会导致 Voronoi 单元格被限制在您的多边形中（其他点不会导致任何交叉点）。

整个算法是并且可以为每个种子并行完成：，然后对于每个种子有一个$O(n\log(n))$$O(n\log(n))$$O(\log(n))$最近邻查询，每个查询结果$O(1)$Sutherland-Hodgman 多边形剪报。