找到经过大多数点的直线的最有效算法是什么？

Question

问题：

在二维平面上给出 N 个点。同一条直线上最多有多少个点？

该问题有 O(N²) 解决方案：遍历每个点并找到与当前点具有相同 dx / dy 的点的数量。将 dx / dy 关系存储在哈希映射中以提高效率。

有没有比 O(N²) 更好的解决方案？

Answer 1

对于这个问题，可能没有比标准计算模型中的 O(n^2) 明显更好的解决方案。

找到三个共线点的问题简化为找到经过最多点的直线的问题，并且找到三个共线点是 3SUM 困难的，这意味着在小于 O(n^2) 的时间内解决它将是一个主要问题理论结果。

请参阅上一个问题 找到三个共线点。

供您参考（使用已知证明），假设我们要回答一个 3SUM 问题，例如在列表 X 中查找 x、y、z，使得 x + y + z = 0。如果我们有一个用于共线点问题的快速算法，我们可以使用该算法来解决 3SUM 问题，如下所示。

对于 X 中的每个 x，创建点 (x, x^3)（现在我们假设 X 的元素是不同的）。接下来，检查创建的点中是否存在三个共线点。

要查看此方法是否有效，请注意，如果 x + y + z = 0，则从 x 到 y 的直线的斜率为

(y^3 - x^3) / (y - x) = y^2 + yx + x ^2

，从 x 到 z 的直线的斜率为

(z^3 - x^3) / (z - x) = z^2 + zx + x^2 = (-(x + y))^2 - (x + y)x + x^2
= x^2 + 2xy + y^2 - x^2 - xy + x^2 = y^2 + yx + x^2

相反，如果从 x 到 y 的斜率等于从 x 到 z 的斜率，则

y^2 + yx + x^2 = z^2 + zx + x^2，

这意味着

(y - z) (x + y + z) = 0，

因此 y = z 或 z = -x - y 就足以证明减少是有效的。

如果 X 中存在重复项，则首先检查任何 x 和重复元素 y 是否为 x + 2y = 0（使用哈希的线性时间或使用排序的 O(n lg n) 时间），然后删除重复项，然后减少到共线寻点问题。

Answer 2

如果将问题限制为穿过原点的线，则可以将点转换为极坐标（角度、距原点的距离）并按角度对它们进行排序。所有具有相同角度的点都位于同一条线上。 O(n logn)

我认为在一般情况下没有更快的解决方案。

Answer 3

霍夫变换可以给你一个近似的解决方案。它是近似的，因为分箱技术在参数空间中的分辨率有限，因此最大分箱将为您提供一些有限的可能线范围。

Answer 4

又是一个带有伪代码的 O(n^2) 解决方案。想法是创建一个以行本身作为键的哈希表。直线由两点（直线与 x 轴相交的点和直线与 y 轴相交的点）之间的斜率定义。

解决方案假设 Java、C# 等语言，其中对象的 equals 方法和 hashcode 方法用于哈希函数。

创建一个包含 3 个字段的对象（调用 SlopeObject）

1. Slope // 可以是无穷大
2. 与 x 轴的交点 -- poix // 将为 (Infinity, some y value) 或 (x value, 0 )
3. 计数

poix 将是一个点 (x, y) 对。如果线穿过 x 轴，则 poix 将（某个数字，0）。如果线平行于 x 轴，则 poix =（无穷大，某个数字），其中 y 值是线与 y 轴相交的位置。
如果 Slope 和 poix 相等，则重写 equals 方法，其中 2 个对象相等。

哈希码被一个函数覆盖，该函数根据 Slope 和 poix 值的组合提供哈希码。下面是一些伪代码

Hashmap map;
foreach(point in the array a) {
    foeach(every other point b) {
        slope = calculateSlope(a, b);
        poix = calculateXInterception(a, b);
        SlopeObject so = new SlopeObject(slope, poix, 1); // Slope, poix and intial count 1.
        SlopeObject inMapSlopeObj = map.get(so);
        if(inMapSlopeObj == null) {
            inMapSlopeObj.put(so);
        } else {
            inMapSlopeObj.setCount(inMapSlopeObj.getCount() + 1);
        }
    }
}
SlopeObject maxCounted = getObjectWithMaxCount(map);
print("line is through " + maxCounted.poix + " with slope " + maxCounted.slope);

Answer 5

使用 p=(a,b) p*:y=a*x + b 的点线对偶变换移动到对偶平面。
现在使用线扫描算法在 NlogN 时间内找到所有交点。
（如果你有一个在另一个之上的点，只需将这些点旋转到某个小角度）。
双平面中的交点对应于底漆平面中的线。

Answer 6

谁说由于 3SUM 对这个问题进行了简化，因此复杂度是 O(n^2)。请注意，3SUM 的复杂度低于此。
请检查 https://en.wikipedia.org/wiki/3SUM 并阅读
https://tmc.web.engr.illinois.edu/reduce3sum_sosa.pdf

Answer 7

正如已经提到的，可能没有比 O(n^2) 更好的方法来解决这个问题的一般情况。但是，如果您假设大量点位于同一条线上（假设点集中的随机点位于具有最大点数的线上的概率为 p）并且不需要精确的算法，随机算法更有效。

maxPoints = 0
Repeat for k iterations:
    1. Pick 2 random, distinct points uniformly at random
    2. maxPoints = max(maxPoints, number of points that lies on the 
       line defined by the 2 points chosen in step 1)

请注意，在第一步中，如果您选择了位于点数最多的线上的 2 个点，您将获得最优解。假设n非常大（即我们可以将找到2个理想点的概率视为放回抽样），则发生这种情况的概率为p^2。因此，经过 k 次迭代后找到次优解的概率为 (1 - p^2)^k。

假设你可以容忍假阴性率rate = err。那么该算法的运行时间为 O(nk) = O(n * log(err) / log(1 - p^2))。如果 n 和 p 都足够大，则这比 O(n^2) 效率更高。 （即假设 n = 1,000,000 并且您知道至少有 10,000 个点位于同一条线上。那么 n^2 将需要 10^12 次操作的量级，而随机算法将需要 10^9 次操作的量级以获得小于 5*10^-5 的错误率。）

Answer 8

$o(n^2)$ 算法不太可能存在，因为问题（甚至检查 R^2 中的 3 个点是否共线）是 3Sum-hard (http://en.wikipedia.org/wiki/3SUM)

Answer 9

这不是一个比 O(n^2) 更好的解决方案，但您可以执行以下操作，

1. 对于每个点转换，首先将其转换为 (0,0) 坐标中的位置，然后对所有点进行等效转换将其他点移动与移动原始选择点所需的相同的 x,y 距离。

2. 将这组新的平移点平移到相对于新的 (0,0) 的角度。

3.保存每个角度的最大点数（MSN）。

4.选择最大存储数量（MSN），即可解决