Suppose there are a set of given points (represented by x and y two 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?

Source code in Python 2.7,

import sys
import random
def distance(p1, p2):
    return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**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]

Suppose there are a set of given points (represented by x and y two 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[0]-p2[0])**2 + (p1[1]-p2[1])**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]