查找所有空三角形

Question

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

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

尽管显而易见的蛮力解决方案对我的小 N 可行，但它具有复杂性 O(N^4)。

您是否知道一种降低时间复杂度的方法，比如说 O(N³) 或 O(N²) 可以使代码保持简单？不允许使用图书馆。

令我惊讶的是，这种三角形的数量相当多。以任意点为中心，通过增加围绕它的角度对其他点进行排序。这形成了一个星形多边形，给出了 N-1 个空三角形，因此总共有 Ω(N²) 个。已经证明这个界限很紧 [具有少量空凸多边形的平面点集，I. Bárány 和 P. Valtr]。

在点形成凸多边形的情况下，所有三角形都是空的，因此O(N³)。快速算法的机会越来越低:(

Answer 1

如果我理解你的问题，那么你正在寻找的是https://en.wikipedia.org/wiki/Delaunay_triangulation

引用上述维基百科文章："The most straightforward way of efficiently computing the Delaunay triangulation is to repeatedly add one vertex at a time, retriangulating the affected parts of the graph. When a vertex v is added, we split in three the triangle that contains v, then we apply the flip algorithm. Done naively, this will take O(n) time: we search through all the triangles to find the one that contains v, then we potentially flip away every triangle. Then the overall runtime is O(n2)."

Answer 2

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)

Answer 3

论文 "Searching for empty Convex polygons" by Dobkin, David P. / Edelsbrunner, Herbert / Overmars, Mark H. 包含一个与解决此问题的可能输出三角形数量成线性关系的算法。

A key problem in computational geometry is the identification of subsets of a point set having particular properties. We study this problem for the properties of convexity and emptiness. We show that finding empty triangles is related to the problem of determininng pairs of vertices that see each other in starshaped polygon. A linear time algorithm for this problem which is of independent interest yields an optimal algorithm for finding all empty triangles. This result is then extended to an algorithm for finding empty convex r-gons (r > 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.

Answer 4

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

依次为每个点构建星形多边形，该多边形通过将其左侧的点围绕它排序而形成。这需要 N 次排序操作（无论如何可以通过排列将其降低到总复杂度 O(N²)）。
计算这个星形多边形内的可见性图并报告由给定点形成的所有三角形。这需要 N 个可见性图构造，总共 M 个操作，其中 M 是空三角形的数量。

很快，通过以所有可能的方式对相应的星形多边形进行三角剖分，从每个点在其左侧构造每个空三角形。

可见性图的构造是星形多边形的特殊版本，它在多边形周围遍历，其中每个顶点都有一个可见性队列，该队列会被更新。

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

查找所有空三角形

Finding all empty triangles

algorithm

computational-geometry