包围点数最多的三角形
Triangle enclosing the biggest number of points
给定一组二维点，找到一个由这些点构成的三角形，该三角形包含最大数量的点。
此算法的粗略算法只是从每个可能的三元组点构建三角形并检查它们包含多少个点，但此解决方案的时间复杂度为 O(n^4)。
为了找到最优解，我想到了先找到这些点的凸包，然后用某种结构在这个包内安排点，但我想不出来。
你对这类问题的最优解有什么想法吗？
在一组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|[=84 的左侧或右侧=] 和 |ca|，这些点被划分为 7 个区域：
如果我们用相邻彩色区域中的点替换三角形的角点，例如点 a 的区域 LRL，我们得到一个更大的三角形，其中包含三角形 abc。如果我们从区域 LRL、LLR 和 RLL 中随机选取三个点，我们可以像这样展开三角形：
然后我们可以使用这个新的三角形再次划分点 a'b'c'（已经在区域 RRR 中的点可以添加到新区域 RRR 而无需检查）和只要区域 LRL、LLR 或 RLL 中至少有一个点，就再次展开三角形。
如果我们在扩展三角形内捕获了足够多的点，我们现在可以使用强力算法，但跳过任何在扩展三角形外没有点的三角形 a'b" c'.
如果我们没有抓到足够多的点使之可行，我们可以用另外三个随机点再试一次。但是请注意，您不应使用包含在多个三角形中的点的并集；每个包含在另一个三角形中但不在同一个三角形中的三个点仍然可以是包含最多点的三角形。
多步排除三角形
我们可以重复随机选择一个三角形，将其展开到最大，然后标记三角形上或三角形内的三个点组成的三角形，然后将它们从检查中排除。这将需要为所有可能的三角形存储一个布尔值，例如在 3D 位数组中，因此它只适用于设置多达几千个点。
为了简化事情，我们可以用一些随机选择的三角形，或者由凸包上的点组成的三角形，或者在 x 或 y 方向上排序时相距很远的点来做这件事，而不是扩展随机三角形, 或 ... 但是这些方法中的任何一种都只能帮助我们找到可以排除的三角形，它们本身不会给我们最佳（甚至足够好）的三角形。
给定一组二维点，找到一个由这些点构成的三角形，该三角形包含最大数量的点。
此算法的粗略算法只是从每个可能的三元组点构建三角形并检查它们包含多少个点，但此解决方案的时间复杂度为 O(n^4)。
为了找到最优解，我想到了先找到这些点的凸包，然后用某种结构在这个包内安排点，但我想不出来。
你对这类问题的最优解有什么想法吗？
在一组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|[=84 的左侧或右侧=] 和 |ca|，这些点被划分为 7 个区域：
如果我们用相邻彩色区域中的点替换三角形的角点，例如点 a 的区域 LRL，我们得到一个更大的三角形，其中包含三角形 abc。如果我们从区域 LRL、LLR 和 RLL 中随机选取三个点，我们可以像这样展开三角形：
然后我们可以使用这个新的三角形再次划分点 a'b'c'（已经在区域 RRR 中的点可以添加到新区域 RRR 而无需检查）和只要区域 LRL、LLR 或 RLL 中至少有一个点，就再次展开三角形。
如果我们在扩展三角形内捕获了足够多的点，我们现在可以使用强力算法，但跳过任何在扩展三角形外没有点的三角形 a'b" c'.
如果我们没有抓到足够多的点使之可行，我们可以用另外三个随机点再试一次。但是请注意，您不应使用包含在多个三角形中的点的并集；每个包含在另一个三角形中但不在同一个三角形中的三个点仍然可以是包含最多点的三角形。
多步排除三角形
我们可以重复随机选择一个三角形，将其展开到最大，然后标记三角形上或三角形内的三个点组成的三角形，然后将它们从检查中排除。这将需要为所有可能的三角形存储一个布尔值，例如在 3D 位数组中，因此它只适用于设置多达几千个点。
为了简化事情，我们可以用一些随机选择的三角形，或者由凸包上的点组成的三角形，或者在 x 或 y 方向上排序时相距很远的点来做这件事，而不是扩展随机三角形, 或 ... 但是这些方法中的任何一种都只能帮助我们找到可以排除的三角形，它们本身不会给我们最佳（甚至足够好）的三角形。