Leo*_*nid 47 algorithm geometry computational-geometry
问题:
在2维平面上给出N个点.同一条直线上的最大点数是多少？
问题有O(N 2)解决方案:遍历每个点并找到dx / dy与当前点相关的点数.将dx / dy关系存储在哈希映射中以提高效率.
有没有比O(N 2)更好的解决这个问题的方法？
jon*_*rry 39
在标准的计算模型中,这个问题可能没有明显优于O(n ^ 2)的解决方案.
找到三个共线点的问题减少了找到穿过最多点的线的问题,找到三个共线点是3SUM-hard,这意味着在小于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 + 2y = 0是否为任何x和重复元素y(使用散列的线性时间或使用排序的O(n lg n)时间),然后删除重复项,然后减少到共线寻点问题.
如果将问题限制为穿过原点的线，则可以将点转换为极坐标（角度、距原点的距离）并按角度对它们进行排序。所有具有相同角度的点都位于同一条线上。O(n logn)
我认为在一般情况下没有更快的解决方案。