algorithm - 包含最大点数的三角形

Question

给定一组 2D 点，找到一个由这些点构建的三角形，它包含最大数量的点。

野蛮算法只是从每个可能的三元组点构建三角形并检查它们包含多少个点，但该解决方案的时间复杂度为 O(n^4)。

对于最佳解决方案，我想首先找到这些点的凸包，并用某种结构在这个包内排列点，但我想不通。

您对此类问题的最佳解决方案有什么想法吗？

Answer 1

在一组n个点中，有(n个选择3)个三角形，用蛮力检查每个点是否包含在每个三角形中确实有O(n4)复杂度。举几个套装尺寸的实际例子:

points:            100              1,000                   10,000
triangles:     161,700        166,167,000          166,616,670,000
checks:     15,684,900    165,668,499,000    1,665,666,849,990,000

下面是一些几何概念；它们不会直接导致解决方案，但它们可以减少必须检查的三角形数量。

凸包的反例

首先，仅使用凸包上的点并不能保证给出最优解。考虑这个反例:



凸包是红色矩形。然而，如果我们用它的两条边和一条对角线组成一个三角形，对角线将穿过中心点簇并遗漏一些点。即使我们只使用矩形的 1 或 2 个角，再加上中心的一个点，它也总是会穿过蓝色三角形并遗漏一些点。凸包上没有点的蓝色三角形实际上是最优解。

三角形中包含的三角形

如果考虑一个三角形 abc，其中包含三个点 d、e 和 f，那么三角形 def 不可能是包含最多点的三角形，因为三角形 abc 至少包含三个点。由 abc 和 def 中的点组合而成的三角形，如 abd，也包含比 abc 少的点。

这意味着找到一个三角形和其中包含的一些点，可以让您丢弃一些三角形。在接下来的段落中，我们将使用这个想法来尽可能多地丢弃需要检查的三角形。

展开三角形

如果我们考虑一个由三个随机选择的点 a、b 和 c(顺时针命名)组成的三角形，然后检查所有其他点是否都在线 |ab|、|bc| 的右侧的左侧。和 |ca|，这些点被划分为 7 个区域:



如果我们用相邻彩色区域中的点替换三角形的角点，例如点 a 的区域 LRL，我们得到一个更大的三角形，其中包含三角形 abc。如果我们从区域 LRL、LLR 和 RLL 中随机选取三个点，我们可以像这样展开三角形:



然后我们可以使用这个新三角形 a'b'c' 再次分割点(已经在区域 RRR 中的点可以添加到新区域 RRR 中而无需检查)并再次扩展三角形，只要其中至少有一个点区域 LRL、LLR 或 RLL。



如果我们在扩展三角形内捕获了足够多的点，我们现在可以使用蛮力算法，但跳过在扩展三角形 a'b"c' 之外没有点的任何三角形。

如果我们还没有捕捉到足够的点来使之可行，我们可以再试一次另外三个随机点。但是请注意，您不应使用包含在多个三角形内的点的并集；三个点都包含在另一个三角形中，但不在同一个三角形中，仍然可以是包含最多点的三角形。

多步排除三角形

我们可以反复选择一个随机三角形，将其最大程度地扩展，然后在三角形上或三角形内标记三个点组成的三角形，然后将这些从检查中排除。这将需要为所有可能的三角形存储一个 bool 值，例如在一个 3D 位阵列中，所以它只适用于多达几千个点的设置。

为了简化事情，我们可以使用一些随机选择的三角形，或由凸包上的点组成的三角形，或在 x 或 y 方向排序时相距较远的点，或...但是这些方法中的任何一种都只能帮助我们找到可以排除的三角形，它们本身不会为我们提供最佳(甚至足够好)的三角形。