Yve*_*ust 9 algorithm computational-geometry
我N在飞机上有一小组点,N < 50.
我想枚举集合中所有三点的点,形成一个不包含其他点的三角形.
即使明显的蛮力解决方案对我的微小也是可行的N,但它具有复杂性O(N^4).
您是否知道一种降低时间复杂度的方法,比方说O(N³)或O(N²)保持代码简单？没有图书馆允许.
令我惊讶的是,这种三角形的数量相当大.将任意点作为中心,并通过增加其周围的角度来对其他点进行排序.这形成一个星形多边形,给出N-1空三角形,因此总共为?(N²).已经证明这个界限很紧[平面点集与少量空凸多边形,I.Bárány和P. Valtr].
在形成凸多边形的点的情况下,所有三角形都是空的O(N³).快速算法的机会越来越低:(
Dobkin,David P./Edelsbrunner,Herbert/Overmars,Mark H.的论文"寻找空的凸多边形"包含了一个线性的可能输出三角形的算法来解决这个问题.
计算几何中的关键问题是识别具有特定属性的点集的子集.我们研究了凸性和空性的这个问题.我们证明找到空三角形与确定在星形多边形中看到彼此的顶点对的问题有关.对于该问题的线性时间算法是独立感兴趣的,产生用于找到所有空三角形的最优算法.然后将该结果扩展到用于找到空凸r-gons(r> 3)和用于确定最大空凸子集的算法.最后,提到了更高维度的扩展.