Efficient Longest arithmetic progression for a set of linear Points

Question

Longest arithmetic progression of a set of numbers {ab₁,ab₂,ab₃ .... ab_n} is defined as a subset {bb₁,bb₂,bb₃ .... bb_n} such that b_i+1 - b_i is constant.

I would like to extend this problems to a set of two dimensional points lying on a straight line. Lets define Dist(P₁,P₂) is the distance between two Points P₁(X₁,Y₁) and P₂(X₂,Y₂) on a line as

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

Now For a given set of points I need to find the largest Arithmetic Progression such that Dist(P_i,P_i+1) is constant, assuming they all lie on the same line (m & C are constant).

I researched a bit but could not figure out an algorithm which is better than O(n²).

In fact currently the way I am doing is I am maintaining a Dictionary say

DistDict=dict()

and say Points are defined in a List as

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

then this is what I am doing

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

so all I have ended up with a dictionary of points which are of equal distance. So the only thing I have to do is to scan through to find out the longest set.

I am just wondering that this ought to have a better solution, but somehow I can't figure out one. I have also seen couple of similar older SO posts but none I can find to give something that is more efficient than O(n²). Is this somehow an NP Hard problem that we can never have something better or if not what approach could be take. Please note I came across a post which claims about an efficient divide and conquer algorithm but couldn't make any head or tail out of it.

Any help in this regard?

Note*** I am tagging this Python because I understand Python better than maybe Matlab or Ruby. C/C++/Java is also fine as I am somewhat proficient in these too :-)

Answer 1

You could study the Fast Fourier Transform methods for multiplication.O(N log N)

You might be able to do something similar with your problem.

Answer 2

Firstly, your definition of distance is wrong. You have to take the square root. Secondly, if you know that all the points lie on a straight line, you can simply ignore the y-coordinates (unless the line is vertical) or the x-coordinates (unless the line is horizontal). Then it reduces to the problem in your first paragraph.

Answer 3

To sum things up: As @TonyK pointed out, if you assume that the points lie on a straight line, you can reduce it to the one-dimensional case that was discussed extensively here already. The solution uses Fast Fourier Transforms as mentioned by @YochaiTimmer.

Additional note: The problem is almost certainly not NP-hard as it has an efficient O(n log n) solution, so that would imply P=NP.