Suppose there are a set of given points (represented by
ytwo dimensional coordinates), and for any given point A, I want to find the nearest distance point among the given set of point.
My current solution is straightforward: just find min among all distances. The issue of my implementation is, if we want to calculate nearest point among the given set of points for another point B, I need to calculate distance again.
My question is, suppose the given set of points are fixed, is there any way to optimize (e.g. pre-process), so that search nearest point is much faster?
import sys import random def distance(p1, p2): return (p1-p2)**2 + (p1-p2)**2 def search_point(points, target_point): result = sys.maxint nearest_point = -1 for p in points: d = distance(p, target_point) if d < result: result = d nearest_point = p return nearest_point if __name__ == "__main__": points =  for i in range(10): points.append((random.randint(0,20),random.randint(0,20))) target_point = (random.randint(0,20), random.randint(0,20)) print 'result', search_point(points, target_point) print 'target_point', target_point print 'raw points', points print 'distances', [distance(p, target_point) for p in points]