一尘不染

找到贯穿大多数点的直线的最有效算法是什么?

algorithm

问题:

在二维平面上给出N个点。同一条 直线 上的最大点数是多少?

该问题具有O(N 2)解:遍历每个点,找到dx / dy与当前点有相同关系的点数。将dx / dy关系存储在哈希图中以提高效率。

有比O(N 2)更好的解决方案吗?


阅读 244

收藏
2020-07-28

共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(在使用哈希的线性时间或使用排序的O(n lg n)时间)中x + 2y =0,然后删除重复项,然后减少到共线的测点问题。

2020-07-28