拥有最终的泰森多边形，是否有可能找到最初的一组点？

Question

我试图找到一种方法来扭转Voronoi算法。

基本上，有一些连接的形状，这主要是由三角形和正方形的，我试图找到一套，使用的Voronoi算法将重新创建初始形状点。

Answer 1

介绍。 此问题已在一份文件，2013年灰和博克在1985年的情况下部分解决您的Voronoi节点都是奇数度则算法由灰和Bolker为你工作之后已经解决了Biedl et al.。

中的所有笔记，有可能不是的点设置，但许多点首先将所有有你问同样的Voronoi图。例如，考虑这幅画

从this website拍摄。红点集和蓝点集给你相同的黑色Voronoi图。 （顺便说一句，红色和蓝色多边形的straight skeletons也与点集的Voronoi图一致。）

该算法的概述。 大致的想法如下。假设一位oracle在Voronoi单元中告诉你一个候选点。然后，您可以通过相邻单元之间的公共边将该点镜像到相邻的Voronoi单元，并继续传播。

但也可能有麻烦：镜像点可能位于相邻小区外。另外，如果你考虑一个Voronoi节点和事件单元格，那么你可以继续在事件Voronoi边缘的一个周期内传播这个点，但是你可能不会再在原始点上结束。

那么什么纸做的是以下几点：

• 它提供的充分必要条件您的输入，形成Voronoi图。

• 它会告诉你如何选择有效的起点，如果这样的点存在。实际上，它给了你所有可能的出发点。

第二部分的工作原理大致如下：对于每个Voronoi单元人知道一个“区域”，其中点具有躺下通过调查电池的沃罗诺伊节点。然后取一个Voronoi图的对偶图的生成树并选择一个任意的根。对于每个细胞，您都有一个“根细胞”的独特“镜像路径”。应用上述区域的镜像序列并交叉镜像。

交集是所有可能起点的集合。如果它是空的，那么你的输入不是Voronoi图。

进一步简化。 如果您的Voronoi节点具有奇怪的程度，那么问题就简单多了。考虑Biedl等人在论文中的图4。为每个节点找出点必须位于的线路。如果一个Voronoi单元有两个奇数度的节点，那么你可以相交这些线并得到一个可能的候选点。你可以为每个Voronoi单元做到这一点。

Answer 2

会不会发现每个三角形的质心给你一个点，根据定义，尽可能远离其他的点可能。