This is a continued discussion from here (Find the nearest point of a given set of points), which I use new approach (bounding box/or envelop algorithm) to improve the algorithm efficiency.

Any code bugs, algorithm time complexity improvement or general code advice is highly appreciated.

Major structure of my code,

1. assign_box is used to build the bounding box or envelop;
2. find_min is finding min points among all candidate points for a given target point, it first use bounding box/envelop solution, if cannot find an answer, it will use brute force solution;
3. bruce_force, a brute force solution, which is used to check the correctness of find_min;
4. distance, utility method, used to check distance of two points.

Source code in Python 2.7,

import sys
import random
from collections import defaultdict
def assign_box(box_map, points, k):
    x_min = min([p[0] for p in points])
    x_max = max([p[0] for p in points])
    y_min = min([p[1] for p in points])
    y_max = max([p[1] for p in points])
    x_distance = (x_max - x_min) / k
    y_distance = (y_max - y_min) / k
    for p in points:
        i = (p[0]-x_min)/x_distance
        j = (p[1]-y_min)/y_distance
        box_map[(i,j)].append(p)

    return (x_min, x_distance, y_min, y_distance)

def distance(p1, p2):
    return (p1[0]-p2[0]) ** 2 + (p1[1]-p2[1]) ** 2

def find_min(points, box_map, target_point, x_min, x_distance, y_min, y_distance):
    # try 9 neighbour first
    row = (target_point[0] - x_min) / x_distance
    col = (target_point[1] - y_min) / y_distance
    result = sys.maxint
    result_point = None
    for r in range(row-1, row+2):
        for c in range(col-1, col+2):
            if (r,c) in box_map:
                for p in box_map[(r,c)]:
                    d = distance(p, target_point)
                    if d < result:
                        result = d
                        result_point = p
    if result_point:
        return (result, result_point)
    else:
        # try brute force solution
        result = sys.maxint
        result_point = None
        for p in points:
            d = distance(p, target_point)
            if d < result:
                result = d
                result_point = p
        return (result, result_point)

def bruce_force(points, target_point):
    result = sys.maxint
    result_point = None
    for p in points:
        d = distance(p, target_point)
        if d < result:
            result = d
            result_point = p
    return (result, result_point)

if __name__ == "__main__":
    # key is a tuple, (box row index, box col index)
    # value is a list of points fall into it
    box_map = defaultdict(list)
    points = []
    for i in range(100):
        points.append((random.randint(0,10), random.randint(0,10)))
    x_min, x_distance, y_min, y_distance = assign_box(box_map, points, 5)
    target_point = (random.randint(0,10), random.randint(0,10))
    print 'target point, ', target_point
    print 'find min result, ', find_min(points, box_map, target_point, x_min, x_distance, y_min, y_distance)
    print 'brute force result, ',  bruce_force(points, target_point)