高效最长算术进程的线性点集

Question

一组数字 {ab₁, ab₂, ab₃ .... ab_n} 中的最长等差数列被定义为一个子集 {bb₁, bb₂, bb₃ .... bb_n}，其中 b_i+1 - b_i 是一个固定的常数。

我想把这个问题扩展到一组位于直线上的二维点。我们定义 Dist(P₁, P₂) 为两个点 P₁(X₁, Y₁) 和 P₂(X₂, Y₂) 之间的距离，计算公式为：

Dist(P₁, P₂) = Dist((X₁, Y₁), (X₂, Y₂)) = (X₂ - X₁)² + (Y₂ - Y₁)²

现在，对于给定的一组点，我需要找到最大的等差数列，使得 Dist(P_i, P_i+1) 是一个固定的值，假设它们都在同一条直线上（m 和 C 是常数）。

我查了一些资料，但没有找到比 O(n²) 更好的算法。

实际上，我现在的做法是维护一个字典，比如说：

DistDict=dict()

而点则定义在一个列表中：

Points = [(X1,Y1),(X2,Y2),....]

然后我做的就是：

for i,pi in enumerate(Points):
    for pj in Points[i+1:]:
         DistDict.setdefault(dist(pi,pj),set([])).add((pi,pj))

所以我最终得到了一个字典，里面存储的是等距离的点。接下来我只需要扫描一下，找出最长的 set。

我在想，这个问题应该有更好的解决方案，但我就是想不出来。我也看过几个类似的旧帖子，但没有找到比 O(n²）更有效的方案。这个问题难道是 NP 难题，以至于我们永远无法找到更好的解决方案，还是说有其他的解决思路呢？

顺便提一下，我看到有个帖子提到了一种高效的 分治算法，但我看不太懂。

在这方面有什么帮助吗？

注意*** 我标记这个问题为 Python，因为我对 Python 比较熟悉，可能不太懂 Matlab 或 Ruby。C/C++/Java 也可以，因为我对这些也有一定的了解 :-)

Answer 1

首先，你对距离的定义是错的。你需要计算平方根。其次，如果你知道所有的点都在一条直线上，你可以简单地忽略y坐标（除非这条线是竖着的）或者x坐标（除非这条线是横着的）。这样问题就变得和你第一段说的那样简单了。

Answer 2

你可以研究一下快速傅里叶变换的方法，这是一种用于乘法运算的技术，效率是O(N log N)。

也许你可以用类似的方法来解决你遇到的问题。

Answer 3

总结一下：正如@TonyK提到的，如果你假设这些点在一条直线上，那么你可以把问题简化成一维的情况，这在这里已经讨论得很透彻。这个解决方案使用了快速傅里叶变换，正如@YochaiTimmer所提到的。

补充说明：这个问题几乎肯定不是NP难题，因为它有一个高效的O(n log n)解决方案，这就意味着P=NP。