从边的列表中生成多边形

Question

在一张由边缘Map<Point, List<Edge>>组成的地图中，给定N个点，能否在O(N log N)时间内得到这些边所形成的多边形？我知道你必须遍历所有的顶点，并获取包含该顶点为起始点的边缘。这些是Voronoi图的边缘，每个顶点最多有3个与之相邻的顶点。因此，在地图中，键是顶点，值是一个列表，其中顶点是起始节点。例如：

点: a,b,c,d,e,f,g
边缘: [a,b]; [a,c]; [a,d], [b,c], [d,e], [e,g], [g,f]
我的想法是逆时针迭代地图，直到我找到初始点。那是一个多边形，然后我把它放在多边形列表中，并继续寻找其他多边形。问题是，我不想超过O(N log N)的复杂度。
谢谢！

- Valentina Ramirez

---

你可能想在这里提问 http://cs.stackexchange.com - pvg

这是否有具体原因不被视为纯图问题（例如，您不希望边相交）？此外，如果您考虑输入为n边形及其所有可能的边和对角线列表，则可以轻松地观察到可能的多边形数量不受“O（N log N）”限制，这意味着在这种情况下，您所追求的复杂度是无法实现的。您对所有多边形感兴趣，还是例如由非相交顶点集组成的多边形？ - Boris Strandjev

当你说一个从点到边的映射时，你是指给定一个点，我可以得到包含该点的所有边吗？还是给定一个点，我可以得到该点是多边形顶点的所有多边形边缘？ - CleoR

你能告诉我们更多关于你的数据吗？这个地图是一堆不相连的多边形还是一个连通的图形呢？ - CleoR

@krish 是的，我正在使用增量算法来获取Delaunay三角剖分，然后是Voronoi图。 - Valentina Ramirez

Answer 1

你可以循环遍历边缘并计算从边缘中点到所有站点的距离。然后按升序对距离进行排序，对于内部Voronoi多边形选择第一和第二个。对于外部多边形，选择第一个。基本上，一条边将2个多边形分开/分割。

这是O(m log n)的算法。

- Micromega

---

我会尝试这样做；但是将这个问题视为图形以获得O（N）或O（N log N）算法也很方便。 - Valentina Ramirez

Answer 2

如果我找到了一个多项式解，我不会在这里发布，因为我相当确定这至少是NP难问题。我认为你最好做DFS。您可能会发现此链接有用Finding all cycles in undirected graphs。

如果您能将图形制成定向图，则可能可以使用以下解决方案。有2 ^ E个有向图（因为每个边可以用2个方向表示）。你可以选择一个随机的有向图，并使用下面的解决方案来查找该图中的所有循环。您可以针对不同的随机有向图多次执行此操作，跟踪所有周期，直到达到令人满意的误差界限。

您可以使用少量状态有效地创建有向图（也许存储与边缘相关的+或-以表示方向？）一旦您第一次以O（n）这样做，您可以随机翻转x << E个方向以在实质上的常数时间内获得新图。

由于您可以在恒定时间内创建后续有向图，因此需要选择运行循环查找算法的次数，以使其仍然是多项式和高效的。

更新-以下仅适用于有向图。

直觉上来说，把问题看做图论问题会更好。你的顶点到边的映射就是图的表示。问题可转化为在图中找出所有环，因为每个环都是一个多边形。我认为“Tarjan强连通分量算法”在这里很有用，因为它可以在O(v+e)的时间内完成。

你可以在这里找到更多关于该算法的信息https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

- CleoR

---

我的图是无向的；你觉得我能用BFS在O(N)的时间内得到那些循环吗？ - Valentina Ramirez

这可能是一个 NP 问题。 - CleoR

所以，如果我使用Tarjan算法，我可以在O（|V|+|E|）的时间内获取所有的多边形，由于有2N-5个顶点和3N-6条边，O（|V|+|E|）= O（5N-11）= O（N）。 - Valentina Ramirez

你认为我可以将它建模为有向图吗？以某些点作为一些线段的起点。 - Valentina Ramirez

@CleoR：我不是专家，但这不是一个非对称旅行推销员问题吗？ - Micromega