Find minimum distance between points of two lists in Python

Question

I have two lists of coordinates:

s1 = [(0,0), (0,1), (1,0), (1,1)]
s2 = [(3,2), (1,9)]

I want to calculate the minimum distance of each point in s1 to any point in s2. e.g. the results should be as follows.

result = [3.60, 3.16, 2.82, 2.23]

Question: What is the most optimized way in terms of execution time, to achieve this result?

So far I've tried this but the execution time is not promising:

import math
def nearestDistance(boundary, p):
    minDistList = map(lambda b: (b[0] - p[0])**2 + (b[1] - p[1])**2, boundary)
    minDist2 = min(minDistList)
    return math.sqrt(float(minDist2))

d = []
for p in s1:
    d.append(nearestDistance(s2, p))

Should I change the structure of s1 and s2 (instead of points use 2d arrays for example)?

Answer 1

To calculate the N distances, there's not a better method than brute forcing all of the possibilities. If you wanted something higher level, like perhaps the greatest or smallest distance, you could reduce the number of calculations based on some external knowledge, but the given your setup, the best you're going to get is O(n^2) performance.

EDIT: Given your comment, there are methods, that involve the general "divide and conquer" approach. Wikipedia has a good overview, and I'll copy a perhaps relevant bit here:

The problem can be solved in O(n log n) time using the recursive divide and conquer approach, e.g., as follows:

1. Sort points according to their x-coordinates.
2. Split the set of points into two equal-sized subsets by a vertical line x = x_mid.
3. Solve the problem recursively in the left and right subsets. This yields the left-side and right-side minimum distances d_Lmin and d_Rmin, respectively.
4. Find the minimal distance d_LRmin among the set of pairs of points in which one point lies on the left of the dividing vertical and the other point lies to the right.
5. The final answer is the minimum among d_Lmin, d_Rmin, and d_LRmin.