find经过大多数点的直线最有效的algorithm是什么？
问题：
N个点在二维平面上给出。 同一条直线上的最大点数是多less？
问题有O（N 2 ）解：经过每个点，找出与当前点具有相同dx / dy的点数。 将dx / dy关系存储在哈希映射中以提高效率。
这个问题比O（N 2 ）有更好的解决scheme吗？
在标准的计算模型中，这个问题可能没有解决scheme，比O（n ^ 2）好得多。
find三个共线点的问题归结为寻找通过最多点的线的问题，find三个共线点是3SUM-hard，这意味着在小于O（n ^ 2）的时间内求解它将是一个主要的理论结果。
查看上一个find三个共线点的问题。
为了您的参考（使用已知的certificate），假设我们想要回答一个3SUM问题，比如find列表X中的x，y，z，使得x + y + z = 0。如果我们有一个快速algorithm来解决共线点问题，我们可以使用该algorithm来解决3SUM问题如下。
对于X中的每个x，创build点（x，x ^ 3）（现在我们假设X的元素是不同的）。 接下来，检查创build点中是否存在三个共线点。
要看到这个效果，请注意，如果x + y + z = 0，那么从x到y的直线的斜率就是
（y ^ 3-x ^ 3）/（y-x）= y ^ 2 + yx + x ^ 2
从x到z的线的斜率是
（z（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，
这意味着
（yz）（x + y + z）= 0，
所以或者y = z或者z = -x – y就足以certificate还原是有效的。
如果在X中有重复项，则首先检查x和y中是否有x + 2y = 0（使用散列的线性时间或使用sorting的O（n lg n）时间），然后删除重复项共线点测问题。
霍夫变换可以给你一个近似的解决scheme。 这是近似的，因为分箱技术的参数空间分辨率有限，所以最大分箱会给你一些有限范围的可能的线。
如果将问题限制在通过原点的线上，则可以将点转换为极坐标（angular度，原点距离）并按angular度对其进行sorting。 所有具有相同angular度的点位于同一条线上。 O（n logn）
在一般情况下，我认为没有更快的解决scheme。
$ o（n ^ 2）$algorithm不太可能存在，因为问题（甚至检查R ^ 2中的3个点是否共线）是3Sum-hard（ http://en.wikipedia.org/wiki / 3SUM ）
再次是一个O（n ^ 2）与伪代码的解决scheme。 想法是创build一个与行本身作为关键的哈希表。 线由两点之间的斜率定义，线切割x轴的点和线切割y轴的点。
解决scheme假定Java，C＃等语言，其中equals方法和对象的哈希码方法用于哈希函数。
用3个字段创build一个对象（调用SlopeObject）
- 坡度//可以是无限的
- 用x轴截取的点 –
poix//将是（无穷大，某个y值）或（x值，0） - 计数
poix将是一个点（x，y）对。 如果直线穿过x轴，那么该poix将（某个数字，0）。 如果线平行于x轴，那么poix =（无穷大，某个数字），其中y值是线与y轴交叉的地方。 当Slope和poix相等时，Override等于方法，其中2个对象相等。
Hashcode被一个函数覆盖，该函数提供了基于Slope和poix值组合的哈希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);
如前所述，可能没有办法比O（n ^ 2）更好地解决这个问题的一般情况。 然而，如果假定大量的点位于同一条线上（比如点集合中的一个随机点位于最大点数的线上的概率是p），并且不需要精确的algorithm，随机algorithm更有效率。
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个点，则会得到最佳解决scheme。 假设n非常大（即我们可以把find2个合意的点的概率看作是replace的抽样），这种情况发生的概率是p ^ 2。 因此，在k次迭代之后find次优解的概率是（1-p ^ 2）^ k。
假设你可以容忍一个错误的负面率=犯错率。 然后这个algorithm在O（nk）= O（n * log（err）/ log（1-p ^ 2））中运行。 如果n和p都足够大，这比O（n ^ 2）更有效。 （即假设n = 1,000,000，并且知道至less有10,000个点位于同一行上，那么在10 ^ 12个操作的幅度上将需要n ^ 2，而随机化algorithm则需要10 ^ 9个操作的幅度得到小于5 * 10 ^ -5的错误率。）
这不是比O（n ^ 2）更好的解决scheme，但是您可以执行以下操作，
- 对于每个点的转换，首先将其转换为（0,0）坐标中的位置，然后通过移动它们移动原始select点所需的相同x，y距离来对所有其他点进行等价转换。
2.将这组新的翻译点翻译成与新（0,0）相关的angular度。
3.保存每个angular度的最大点数（MSN）。
4.select最大存储号码（MSN），这将是解决scheme
