def make_kd_tree(points, dim, i=0):
    """
    Build a KD-Tree for fast lookup.
    Based on a recipe from code.activestate.com
    """
    if len(points) > 1:
        points.sort(key=lambda x: x[i])
        i = (i + 1) % dim
        half = len(points) >> 1
        return (
            make_kd_tree(points[: half], dim, i),
            make_kd_tree(points[half + 1:], dim, i),
            points[half])
    elif len(points) == 1:
        return (None, None, points[0])