问找到所有的空三角形

EN

本文提出了一种求解这一问题的算法，该算法以可能的输出三角形数为线性。

计算几何中的一个关键问题是对具有特殊性质的点集子集的识别。我们研究这个问题的性质是凸性和空性。我们证明了寻找空三角形与确定星形多边形中相互看见的顶点对的问题有关。该问题的线性时间算法是一个独立的问题，它给出了一个寻找所有空三角形的最优算法。然后将此结果推广到寻找空凸r-龙(r > 3)和确定最大空凸子集的算法中。最后，给出了高维的扩展。

Dobkin、Edelsbrunner和Overmars的算法草图如下：

• 对每一点依次，建立星型多边形形成围绕它周围的点在其左边。这需要N个排序操作(至少可以通过一种安排降低到总复杂度O(N 2))。
• 计算这个星形多边形内的可见性图，并报告与给定点形成的所有三角形。这需要N个可见性图的构造，对于总共的M操作，其中M是空三角形的数目。

很短的时间内，从每一点开始，你就可以用各种可能的方式来构造它左边的每个空三角形，通过对相应的星形多边形进行三角剖分。

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

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

​

​

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 )时间内完成，因此复杂度为O(N^3 log )。