寻找所有空三角形

Question

我在平面上有一小组N个点，其中N < 50。

我想枚举集合中形成不包含其他点的三角形的所有三元组。

虽然显而易见的暴力解决方案对于我的这个小N可能是可行的，但它的复杂度为O(N^4)。

您知道降低时间复杂度的方法吗？例如降到O(N³)或O(N²)，并保持代码简单？ 不允许使用库。

---

令人惊讶的是，这样的三角形数量相当大。以任意一个点为中心，并按其周围角度递增排序其他点。这形成了一个星形多边形，提供了N-1个空三角形，因此总共有Ω(N²)个三角形。已经证明此界限是紧的[Planar Point Sets with a Small Number of Empty convex Polygons，I. Bárány和P. Valtr]。

对于形成凸多边形的点，所有三角形都是空的，因此为O（N³）。快速算法的机会正在降低 :(

- user1196549

---

@MrBones：有N(N-1)N(2)/3个可能的三角形。 - user1196549

@MrBones：你是怎么解决这个问题的？ - High Performance Mark

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - ale64bit

@YvesDaoust 哦，我误解了。您有一组点P，并且您想要所有顶点为P中点的三角形。我的错。我把它看成平面上的点。 - Squidly

@YvesDaoust：对我来说，枚举三元组就是列出任何三元组。 - Squidly

Answer 1

这篇论文《搜索空凸多边形》(Searching for empty Convex polygons)通过一个线性算法解决了此问题，该算法的时间复杂度与可能输出的三角形数量成正比。

在计算几何中，关键问题是识别点集的子集是否具有特定属性。我们研究了凸性和空性的这个问题。我们发现寻找空三角形与确定星形多边形中彼此可见的顶点对的问题相关。对于这个问题，我们提供了一个独立兴趣的线性时间复杂度算法，它给出了找到所有空三角形的最优算法。然后将此结果扩展到找到空凸r-gons（r > 3）的算法，并确定最大的空凸子集。最后，还提到了更高维度的扩展。

- Peter de Rivaz

---

非常有趣。他们声称有一种最优方法，其运行时间与空三角形的数量呈线性关系（即N²到N³）。它使用可见性图。由于该方法旨在用于具有“r”边的多边形，因此需要将其专门化（希望能够简化）到“r=3”的情况。 - user1196549

Answer 2

Dobkin、Edelsbrunner和Overmars提出的三角形算法草图如下：

• 轮流对每个点进行操作，构建由其左侧的点排序形成的星形多边形。这需要进行N次排序操作（可以通过排列将总复杂度降至O（N²））。
• 计算此星形多边形中的可见图，并报告给定点所形成的所有三角形。这需要进行N次可视图构造，共计M次操作，其中M是空三角形的数量。

简而言之，从每个点开始，您可以通过以所有可能的方式三角化相应的星形多边形在其左侧构建每个空三角形。

可见图的构建是针对星形多边形的特殊版本，它在沿着多边形遍历时工作，在此过程中，每个顶点都有一个可见性队列，该队列会得到更新。

该图显示了蓝色的星形多边形及其可见图的边缘。轮廓线生成6个三角形，内部可见性边缘生成其中的8个三角形。

- user1196549

Answer 3

for each pair of points (A, B):
    for each of the two half-planes defined by (A, B):
        initialize a priority queue Q to empty.
        for each point M in the half plane, 
            with increasing angle(AB, AM):
            if angle(BA, BM) is smaller than all angles in Q:
                print A,B,M
            put M in Q with priority angle(BA, BM)

在优先队列中插入和查询最小值都可以在O(log N)时间内完成，因此这种方式的复杂度为O(N^3 log N)。

- galath

---

我不理解“对于每个半平面”——这个集合中有哪些半平面？ - j_random_hacker

@j_random_hacker：每一对点都定义了一条直线，因此有两个半平面，其中一个是按照惯例选择的。 - user1196549

感谢您的提议。@PeterdeRivaz引用的论文值得一看。 - user1196549

@YvesDaoust：所以，“对于每个半平面”是指“对于由（A，B）定义的2个半平面中的每一个”？ - j_random_hacker

@j_random_hacker：我也这么认为。 - user1196549

Answer 4

如果我理解您的问题，您要找的是https://en.wikipedia.org/wiki/Delaunay_triangulation。

引用自维基百科文章：“计算Delaunay三角剖分最直接的方法是重复一次添加一个顶点，重新对图形的受影响部分进行三角剖分。当添加一个顶点v时，我们将包含v的三角形分成三个部分，然后应用翻转算法。如果朴素地完成，这将需要O(n)时间：我们搜索所有三角形以找到包含v的三角形，然后我们可能会翻转每个三角形。然后总运行时间为O(n2)。”

- fearless_fool

---

你将如何使用三角测量来搜索所有没有内部点的三角形？ - ale64bit

正确，但它没有列出所有可能的这样的三角形。 - ale64bit

我了解Delaunay三角剖分。但是它不符合我的问题陈述，因为它对三角形强制执行更严格的条件（不允许在外接圆内有点）。【我没有给你投反对票】 - user1196549

抱歉——我误解了你的问题。（我擅长吸引踩票——别担心！ :) 但现在我想知道是否有一种改编的 Delaunay 技术可以满足你的需求。增加半径？ - fearless_fool

@fearless_fool：可能不行，因为这个问题不会生成三角剖分，而是一组重叠的三角形。 - user1196549