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

Question

问题:

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

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

是否有比O（N²）更好的解决方案？

- Leonid

---

不认为这是可能的。如果存在一种在单个点上有帮助的转换，那么这将是可能的，但不幸的是我能想到的任何转换都需要2个点。概率方法（如蒙特卡罗）可能更快，但不能保证它找到最大值。 - ruslik

如果您将点坐标代入线性方程 k*x[i] + b = y[i]，您将得到关于 k 和 x 的方程。在 {k,x} 空间中，它将成为一条直线。因此，这就成为了一个通过一个点的最大直线数量的问题。它可能有解决方案。 - Vovanium

请注意，该问题仅适用于整数坐标，因此 k 和 b 必须是有理数，使得 b == y - k*x，其中 y 和 x 是整数。也许通过将问题转化为“找到满足大多数方程的这样的有理数 b 和 k”的形式会有所帮助。 - ruslik

@leonid，你认为dx/dy足够吗？我认为dx/dy仅代表斜率，那截距y-intercept呢？ - Jack

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）的时间内进行），然后在缩小到共线点查找问题之前删除重复项。

- jonderry

---

好答案。我在面试中被问到这个问题，给了一个O(n^2)的答案，感觉很糟糕。你的答案让我从“:'(”变成了“:D”。 - Marcel Valdez Orozco

假设点为（x，x^3）有什么特别之处？为什么对于（x，x^2）这样的点数学计算不起作用？ - gjain

我本来要问的是什么保证这3条线的y截距也是相同的（即，答案只显示斜率将相同），但后来恍然大悟：如果两条线具有相同的斜率并通过某个共同点，那么它们必定是同一条线——而这就是这里所有3条可能的线的情况（xy和xz具有相同的斜率并共享x，而yz具有与xz相同的斜率并与xz共享z）。 - j_random_hacker

这个已经在某个地方实现了吗？比如说用Python？ - user32882

Answer 2

如果将问题限制在通过原点的直线上，你可以将点转换为极坐标（角度，距离原点的距离）并按角度排序。所有具有相同角度的点位于同一条直线上。O(n logn)

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

- Erwin J.

---

实际上，如果将问题限制为穿过原点（0,0）的直线，可以使用哈希在O(n)时间内解决。 - Marcel Valdez Orozco

Answer 3

霍夫变换可以给出近似解。它是近似的，因为分箱技术在参数空间中具有有限的分辨率，所以最大的箱子只会给出一定范围内可能的直线。

- ergosys

Answer 4

再次提供一个O(n^2)的伪代码解决方案。思路是创建一个哈希表，以线本身作为键。线由两点之间的斜率、线与x轴相交的点和线与y轴相交的点来定义。

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

创建一个带有3个字段的对象（称为SlopeObject）：

1. Slope //可以是无穷大 2. 与x轴相交的点--poix //将是(无穷大，某个y值)或(x值，0) 3. Count poix将是一个点(x,y)对。如果线穿过x轴，则poix将是一些数字和0。如果线平行于x轴，则poix=(无穷大，某个数字)，其中y值是线穿过y轴的位置。

重写equals方法，其中当Slope和poix相等时，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);

- Dheerendra Kulkarni

Answer 5

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

- Shlomo Pongratz

---

“交点”是指什么与什么的交集？ - Will Ness

请参考链接中第9页的示例，对双重平面中的线进行操作。 http://graphics.stanford.edu/courses/cs268-16-fall/Notes/cmsc754-lects.pdf - Shlomo Pongratz

Answer 6

有人说，由于3SUM问题可以转化为此问题并且复杂度为O(n^2)，所以该问题的复杂度也是O(n^2)。但请注意，3SUM问题的复杂度低于该问题。 请查看https://en.wikipedia.org/wiki/3SUM并阅读https://tmc.web.engr.illinois.edu/reduce3sum_sosa.pdf。

- Shlomo Pongratz

---

你想表达什么并不清楚，尤其是第二句话不完整。 - Floyd

缺少单词 less。 - Shlomo Pongratz

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)

请注意，在第一步中，如果您选择的两个点位于具有最大点数的线上，则会得到最佳解决方案。假设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的误差率。）

- Tony Cai

Answer 8

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

- user695652

Answer 9

这并不是比O(n^2)更好的解决方案，但你可以按照以下步骤进行：

1. 对于每一个点，先将其转换为似乎在(0,0)坐标处，然后通过移动其他所有点相同的x,y距离来进行等效平移。

2.将这组新的翻译点相对于新的(0,0)角度进行翻译。

3.保持最大数(MSN)，即每个角度中存在的点数。

4.选择已存储的最大数(MSN)，这将是解决方案。

- mariana soffer

---

但这仍然是O(n^2)的，而且比OP的方法更复杂实现。 - Ben Lee

你需要遍历每个点一次，这是一个n，然后你需要对相同角度的点进行排序和计数，这算另一个n吗？我不确定，请原谅我。 - mariana soffer

“对于每个点”和“对于所有其他点”，意味着在n-1个点上运用一个操作n次。这是O(n^2)的时间复杂度。 - Matthieu M.

现在我清楚地理解了，Matthieu，非常感谢您的解释。 - mariana soffer

这个答案应该解释一下，它并不比原帖的回答更好，反而会产生误导。 - Marcel Valdez Orozco