voronoi图的逆

Question

我在地理信息系统工作。我有一组多边形。我想做一个算法，首先检查多边形集是否是一个有效的Voronoi图。如果是，则返回一组点，可以生成相同的voronoi图。

有人能帮我怎么做吗？

谢谢

Answer 1

这个所以回答的简短摘要使用了Thiessen多边形而不是Voronoi图：

这个问题已经通过Biedl等人解决了，识别直骨架和Voronoi图并重构它们的输入，ISVD，2013年。

对于一些特殊情况，这个问题要简单一些，但是对于一般的输入，这个问题就不那么简单了。请注意，对于某些输入，可能存在无穷多个解，即具有相同Voronoi图的点集：

​

​

Biedl等人的论文。给出了一种算法，该算法(i)检查多边形图解是否为Voronoi图，(ii)确定其Voronoi图与之相等的所有可能的点集。

其基本思想是:考虑Voronoi图对偶的根生成树，并继续将Voronoi节点的局部约束传播到根Voronoi区域。这些限制的交集给出了所有可能的解决方案。

请参阅其他所以回答中的详细信息。