三角形包围着最多的点数

Question

给定一组2D点找到从这些点构建的三角形,其包含最大数量的点.

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

为了获得最佳解决方案,我想到了首先找到这些点的凸包并在这个船体内部安排一些结构,但我无法弄明白.

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

Answer 1

在n个点的集合中，有（n选3）个三角形，并且使用蛮力来检查每个点是否包含在每个三角形中确实具有O(n ⁴ )复杂度。举几个集合大小的实际例子：

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'之外没有点的任何三角形。

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

多步排除三角形

我们可以重复选择一个随机三角形，将其最大化，然后标记由三角形上或内部的三个点组成的三角形，然后将它们从检查中排除。这将需要为所有可能的三角形存储一个布尔值，例如在3D位数组中，因此仅对于最多几千个点的设置是可行的。

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