c++ - 一组线性点的有效最长算术级数

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₂) 在一条线上作为

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

现在对于一组给定的点，我需要找到最大的算术级数，使得 Dist(P_i,P_i+1) 是常数，假设它们都是位于同一条线上(m 和 C 是常数)。

我研究了一下，但找不到比 O(n²) 更好的算法。

事实上，目前我正在做的是维护一个 Dictionary say

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。

我只是想知道这应该有更好的解决方案，但不知何故我想不出一个。我也看过一些类似的旧 SO 帖子，但我找不到比 O(n²) 更有效的东西。这是否是一个 NP Hard 问题，我们永远无法拥有更好的东西，或者如果没有，可以采取什么方法。请注意，我遇到了一个声称高效 divide and conquer algorithm 的帖子但无法从中得出任何结论。

在这方面有什么帮助吗？

注意*** 我标记这个 Python 是因为我比 Matlab 或 Ruby 更了解 Python。 C/C++/Java 也不错，因为我也比较精通这些:-)

Answer 1

总结一下:正如@TonyK 所指出的，如果您假设点位于一条直线上，则可以将其简化为一维情况，即 discussed extensively here已经。该解决方案使用@YochaiTimmer 提到的快速傅里叶变换。

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