Nearest-neighbour search and backtracking

After this page, you should be able to:

• Trace the best-so-far candidate and decide whether a far region can still improve it.

• Use the updated distance after near-side search rather than treating the first candidate as final.

Builds on: Spatial bounds justify exclusion; they are not exact object distances.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

JavaScript points are arrays compared by same_point; Julia points are value tuples. Julia coordinate/child indices are one-based (x=1, y=2; SW/SE/NW/NE=1/2/3/4), while depth still starts at zero. R-tree orientation uses exact big-integer arithmetic for the supplied integer-coordinate geometry; nearest distances remain floating calculations. General R-tree update code is still conceptual in every language.

A nearby path is only a starting point¶

Nearest-neighbour search asks which stored point minimises distance to a query point; it does not ask for exact equality. Descend into the side containing the query first to obtain a promising candidate, but keep a best-so-far point and distance. Another side can still contain a closer point.

For two-dimensional Euclidean distance, compare squared distances:

Squaring avoids square roots without changing which distance is smallest. This page extends the lecture’s conceptual introduction with a complete teaching implementation.

Use a lower bound to decide whether to cross the split¶

At an active-axis split $s$, every point on the other side is at least $|q_{axis}-s|$ away in that coordinate. If its squared value exceeds the current best squared distance, that entire far side cannot improve the result.

In the picture, root (5,0) splits x at 5, query Q = (4.9,5) goes left to (1,5), but the nearest stored point is (5.1,5) on the right. The split distance is 0.1, smaller than the current best distance 3.9 after the left visit, so the right side remains a candidate.

Search the near side, then reconsider the far side¶

def kd_nearest(root, query):
    best_point = None
    best_d2 = float("inf")

    def visit(node, depth):
        nonlocal best_point, best_d2
        if node is None:
            return
        p = node.point
        d2 = sum((p[i] - query[i]) ** 2 for i in range(2))
        if best_point is None or d2 < best_d2:
            best_point, best_d2 = p, d2
        axis = depth % 2
        delta = query[axis] - p[axis]
        if delta < 0:
            near, far = node.left, node.right
        else:
            near, far = node.right, node.left
        visit(near, depth + 1)
        if delta * delta <= best_d2:
            visit(far, depth + 1)

    visit(root, 0)
    return best_point

function kd_nearest(root,query) {
    let best_point=null, best_d2=Infinity;
    function visit(node,depth) {
        if (node===null) return;
        const p=node.point, d2=(p[0]-query[0])**2+(p[1]-query[1])**2;
        if (best_point===null || d2<best_d2) { best_point=p; best_d2=d2; }
        const delta=query[depth%2]-p[depth%2];
        const near=delta<0 ? node.left : node.right, far=delta<0 ? node.right : node.left;
        visit(near,depth+1);
        if (delta*delta<=best_d2) visit(far,depth+1);
    }
    visit(root,0); return best_point;
}

function kd_nearest(root,query)
    best_point=nothing; best_d2=Inf
    function visit(node,depth)
        node===nothing && return
        p=node.point; d2=sum((p[i]-query[i])^2 for i in 1:2)
        if best_point===nothing || d2<best_d2; best_point=p; best_d2=d2; end
        axis=mod(depth,2)+1; delta=query[axis]-p[axis]
        near,far=delta<0 ? (node.left,node.right) : (node.right,node.left)
        visit(near,depth+1)
        delta^2<=best_d2 && visit(far,depth+1)
    end
    visit(root,0); return best_point
end

The far-side test uses the updated best distance after the near-side recursion. nonlocal allows inner calls to update the shared candidate held by this query; no state is shared across separate function calls. Return None for an empty tree. For equal nearest distances, this implementation keeps the first point encountered, so it promises one nearest point rather than a particular tie order.

A skipped region needs proof, not a guess¶

Every visited point can improve the candidate. Every skipped far region has a valid distance lower bound larger than the current best distance, so it cannot contain a better answer. These two facts justify returning the final candidate.

The split-plane bound is safe but may be loose. Distance to the whole inherited bounding rectangle can provide a stronger bound when those rectangles are maintained. Good pruning can reduce visits substantially, but the worst case still visits $O(n)$ nodes, with $O(h+1)$ recursive stack space. Exact search’s one path does not establish the nearest-neighbour result.

Check your understanding¶

Predict the answer before opening the explanation.

1. In the illustrated example, Q=(4.9,5) has visited left point (1,5). Should it cross the x=5 split? Which shown point is actually nearest?

2. A far-region squared lower bound is 4. Before searching near, the best squared distance is 9; afterward it is 1. Should that far region still be searched?

Concept reference: Princeton’s description of region-based range and nearest-neighbour pruning. Continue to k-d deletion and operation costs before moving to point quadtrees, or return to the spatial-search overview.