问题:
在二维平面上给出N个点。同一条 直线 上的最大点数是多少?
该问题具有O(N 2)解:遍历每个点,找到dx / dy与当前点有相同关系的点数。将dx / dy关系存储在哈希图中以提高效率。
dx / dy
有比O(N 2)更好的解决方案吗?
在标准计算模型中,可能没有比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(在使用哈希的线性时间或使用排序的O(n lg n)时间)中x + 2y =0,然后删除重复项,然后减少到共线的测点问题。