Find maximum equidistant points on a line

0
votes

I need an algorithm to find maximum no of equidistant points on the same line.

Input: List of collinear points

For example: My points could be

[(1, 1), (1, 2), (1, 3)]

In this case what I could do is sort the points based on their distance from origin and find the distance sequentially. However, in a scenario such as below the condition is failing. All the points are on the same line y=-x+6, and are equidistant from each other.

[(3, 3), (2, 4), (4, 2), (5, 1), (1, 5)]

because all the points are equidistant from origin, and sorting order could be anything so sequential traversal is not possible. For example, if final dictionary become this [(3, 3), (5, 1), (4, 2), (2, 4), (1,5)] we would end up calculating distance between (3,3) and (5,1), which is not correct. Ideally, I would want to calculate the distance between closest points so the order should be (1,5), (2,4).

To overcome this problem I created a O(n*n) solution by iterating using 2 loops, and finding frequency of minimum distance between any 2 points:

import sys
distance_list=[]
lop=[(1, 3), (2, 4), (3, 5), (4, 6), (10, 12), (11, 13), (12, 14), (13, 15), (14, 16)]
lop.sort(key=lambda x: x[0]*x[0] + x[1]*x[1])
for k in range(0, len(lop)):
    min_dist=sys.maxint
    for l in range(0, len(lop)):
        if k!=l:
            temp_dist = ( (lop[k][0] - lop[l][0])*(lop[k][0] - lop[l][0]) + (lop[k][1] - lop[l][1])*(lop[k][1] - lop[l][1]) )
            min_dist= min(min_dist, temp_dist)
    distance_list.append(min_dist)

print distance_list.count (max(distance_list,key=distance_list.count))

However, above solution failed for below test case:

[(1, 3), (2, 4), (3, 5), (4, 6), (10, 12), (11, 13), (12, 14), (13, 15), (14, 16)]

Expected answer should be: 5 However, I'm getting: 9

Essentially, I am not able to make sure, how do I do distinction between 2 cluster of points which contain equidistant points; In the above example that would be 

[(1, 3), (2, 4), (3, 5), (4, 6)] AND [(10, 12), (11, 13), (12, 14), (13, 15), (14, 16)]
2
pythonalgorithm
Could you provide some code to show what you try please? – Nuageux
What do you mean failing? if they are all equidistant from the origin any order is the right order for sorting...it's like sorting an array of the same number – depperm
And I need an algorithm to solve the travelling salesmen problem. – DeepSpace
@DeepSpace Perhaps you could ask your own question, then. – chepner
@Nuageux added the code – Geek

2 Answers

2
votes

If you want to put the points in order, you don't need to sort them by distance from anything. You can just sort them by the default lexicographic order, which is consistent with the order along the line:

lop.sort()

Now you just need to figure out how to find the largest set of equidistant points. That could be tricky, especially if you're allowed to skip points.

0
votes

because you want the distance of consecutive points, there is no need to calculate all combinations, you just need to calculate the distance of (p0,p1), (p1,p2), (p2,p3), and so on, and group those pairs in that order by the value of their distance, once you have done that, you just need the longest sequence among those, to do that the itertools module come in handy

from itertools import groupby, tee, izip  

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)

def distance(a,b):
    ax,ay = a
    bx,by = b
    return (ax-bx)**2 + (ay-by)**2

def longest_seq(points):
    groups = [ list(g) for k,g in groupby(pairwise(points), lambda p:distance(*p)) ]
    max_s = max(groups,key=len)  # this is a list of pairs [(p0,p1), (p1,p2), (p2,p3),..., (pn-1,pn)]
    ans = [ p[0] for p in max_s ] 
    ans.append( max_s[-1][-1] ) # we need to include the last point manually 
    return ans

here the goupby function group together consecutive pairs of points that have the same distance, pairwise is a recipe to do the desire pairing, and the rest is self explanatory.

here is a test

>>> test = [(1, 3), (2, 4), (3, 5), (4, 6), (10, 12), (11, 13), (12, 14), (13, 15), (14, 16)]
>>> longest_seq(test)
[(10, 12), (11, 13), (12, 14), (13, 15), (14, 16)]
>>>