algorithm - 查找所有空三角形

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

论文"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.