1

I have a list l which holds n number of points. Each element in the list is a point with x-coordinate and y-coordinate. I am trying to find out the quickest way with which I can find the maximum of all possible distances between the elements in the list l.

To be precise Let the list l be 

l = [(1,2),(5,3),(6,9)]

If 

d((1,2),(5,3)) = 1,  
d((5,3),(6,9)) = 2,  
d((6,9),(1,2)) = 5

where d is my distance function, my solution is 5 that is maximum of all possible distances between any pair of points in the list.

I appreciate any help.

Ram's stack
  • 307
  • 1
  • 5
  • 16
  • 5
    Do try something before asking someone else for the code directly. Add some code that you have tried, the errors you got if any. Stackoverflow does not provide you with complete code – Bhargav Rao Sep 21 '15 at 18:21
  • It looks like you have the pseudocode worked out. You will want to take the distance function d^2 = (x_2-x_1)^2 + (y_2-y_1)^2 for all x,y. – Shawn Mehan Sep 21 '15 at 18:24
  • I am not expecting the code bro. A suggestion should be fine for me. I can try coding it and extend the query if I face any issues. Thank You! @Bhargav Rao – Ram's stack Sep 21 '15 at 18:24
  • 2
    Finding the [convex hull](https://en.wikipedia.org/wiki/Gift_wrapping_algorithm) would probably be a good start. – Kevin Sep 21 '15 at 18:26
  • @Kevin I will try working on it. The concept seems interesting. – Ram's stack Sep 21 '15 at 18:36
  • 1
    @Shawn: The question contains no code, pseudo- or otherwise (except for some assignment statements). – martineau Sep 21 '15 at 18:50
  • @martineau, foolishly, i was attempting to be constructive and positive in my encouragement. **sighs** – Shawn Mehan Sep 21 '15 at 18:58
  • 1
    what is your distance function? – Padraic Cunningham Sep 21 '15 at 19:13

3 Answers3

1

Can you use numpy and scipy? scipy.spatial.distance.cdist seems to do what you want. And by experience, it also solves it extremely quickly even if there are hundreds of thousands of points, which would basically choke pure python.

Find the Euclidean distances between four 2-D coordinates:

>>> from scipy.spatial import distance
>>> coords = [(35.0456, -85.2672),
...           (35.1174, -89.9711),
...           (35.9728, -83.9422),
...           (36.1667, -86.7833)]
>>> dists = distance.cdist(coords, coords, 'euclidean')
>>> dists
array([[ 0.    ,  4.7044,  1.6172,  1.8856],
       [ 4.7044,  0.    ,  6.0893,  3.3561],
       [ 1.6172,  6.0893,  0.    ,  2.8477],
       [ 1.8856,  3.3561,  2.8477,  0.    ]])

To find the maximum distance, you can just use numpy's max function.

>>> import numpy as np
>>> np.max(dists)
6.089281104531147

So in your case:

>>> l = [(1,2),(5,3),(6,9)]
>>> np.max(distance.cdist(l, l, "euclidean"))
8.602325267042626

It is not 5, but I'm guessing you gave arbitrary values for the result of d?

Jean Nassar
  • 555
  • 1
  • 5
  • 13
0

To get all combinations of the points you can use itertools

for p0, p1 in itertools.combinations(list, 2):
    print( d(p0,p1) )

will print you all (three is this case) distances. Finding the max left as an exercise...

karakfa
  • 66,216
  • 7
  • 41
  • 56
  • I don't think O(n^2) would be considered efficient – Padraic Cunningham Sep 21 '15 at 18:50
  • Efficient in development time, ease of maintenance and clarity of the code. – karakfa Sep 21 '15 at 18:51
  • Yeah, OP never defined which eval criteria were going to be used to determine efficiency. – Shawn Mehan Sep 21 '15 at 18:59
  • 2
    @ShawnMehan, *What would be the fastest way to find the maximum of all possible distances between any pair of points in a list.* – Padraic Cunningham Sep 21 '15 at 19:07
  • I'm not disagreeing with you that it's O(n^2). I'm just saying that the OP never really stated what kind of efficiency that they were looking for. Fastest way could be the smallest number of characters that one has to type into a homework assignment that one couldn't be arsed doing :) – Shawn Mehan Sep 21 '15 at 19:21
0
>>> max(((i,j,dist(i,j)) for i,j in itertools.combinations(l, 2)), key=lambda x:x[2])
((5, 3), (6, 9), 13)
Sait
  • 19,045
  • 18
  • 72
  • 99