在 3D 中找到最大数量的共线点

Finding biggest number of collinear points in 3D

我接到了一项任务,我必须找到一条直线,该直线经过给定集合中最多的点 (>5000)。

我能够通过连接 2 个点并检查每个其他点是否共线来解决问题,但这是一个 O(N^3) 算法。

我想知道是否有办法让我的程序 运行 优于 O(N^3).

您可以在 O(n^2) 中使用散列来完成。

  • 对每对2点求出它们定义的直线方程O(n^2)

    • 将这些等式放入散列中 O(1)(平均复杂度),以便计算每个等式的出现次数。
  • 遍历所有哈希方程并找到计数最多的那个 O(n ^ 2)。这是您要搜索的行。

alg 的总时间复杂度:O(n^2) * O(1) + O(n^2) = O(n^2)

棘手的一点是,由于浮点精度,同一行似乎有 2 个不同的方程式。您需要找到一个考虑到这一点的哈希函数。


另一种方法是:

  • 将方程放入向量中O(n^2)
  • 对向量进行排序O(n^2 log(n^2) = O(n^2 log n)
  • 然后最终找到最长的等式序列O(n ^ 2).

最终的复杂度为 O(n^2 log n)