Range search and safe pruning

After this page, you should be able to:

• Choose every child region that can intersect a closed query, including split-coordinate equality.

• Distinguish point tests, subtree pruning and the cost of reporting results.

Builds on: Exact lookup follows one path; range reporting may need more than one.

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.

Report all points inside an inclusive rectangle¶

Let low = (xmin, ymin) and high = (xmax, ymax), with lower bounds no larger than upper bounds. A point belongs to the query if both coordinate comparisons lie inside the closed intervals. Points on an edge or corner count as inside.

The shared query is low = (1, 2), high = (4, 7). It reports B = (2, 7), D = (1, 3) and E = (3, 6).

Test the point and the child regions separately¶

At an active-axis split $s$, query interval $[l,u]$ can reach:

If l == s, the left region contains no answer because all its coordinates are strictly below the query. If u == s, the right region can contain equal-coordinate matches and must not be skipped. Both branches may be necessary when the query straddles the split.

The current point being outside the rectangle does not justify pruning both children. Root A = (5, 4) is outside the shared query but its left descendants contain every answer.

Traverse every region that can still contribute¶

def kd_range(root, low, high):
    if any(low[i] > high[i] for i in range(2)):
        raise ValueError("lower bounds must not exceed upper bounds")
    out = []

    def visit(node, depth):
        if node is None:
            return
        p = node.point
        if all(low[i] <= p[i] <= high[i] for i in range(2)):
            out.append(p)
        axis = depth % 2
        if low[axis] < p[axis]:
            visit(node.left, depth + 1)
        if high[axis] >= p[axis]:
            visit(node.right, depth + 1)

    visit(root, 0)
    return out

function kd_range(root,low,high) {
    if (low.some((x,i)=>x>high[i])) throw new RangeError("reversed bounds");
    const out=[];
    function visit(node,depth) {
        if (node===null) return;
        const p=node.point, axis=depth%2;
        if (p.every((x,i)=>low[i]<=x && x<=high[i])) out.push(p);
        if (low[axis]<p[axis]) visit(node.left,depth+1);
        if (high[axis]>=p[axis]) visit(node.right,depth+1);
    }
    visit(root,0); return out;
}

function kd_range(root,low,high)
    any(low[i]>high[i] for i in 1:2) && throw(ArgumentError("reversed bounds"))
    out=Any[]
    function visit(node,depth)
        node===nothing && return
        p=node.point; axis=mod(depth,2)+1
        all(low[i]<=p[i]<=high[i] for i in 1:2) && push!(out,p)
        low[axis]<p[axis] && visit(node.left,depth+1)
        high[axis]>=p[axis] && visit(node.right,depth+1)
    end
    visit(root,0); return out
end

This function checks the current point, then visits left before right when permitted. It returns traversal order, not sorted order or distance order. The output list is created separately for each call, avoiding a shared mutable default argument.

Account for visited nodes and reported results¶

The shared query visits A, B, D and E. At A it explores only left. At B both regions could intersect, although its right child is empty. At D it skips the left region because the query’s lower x bound equals the split x = 1, and visits E on the right. The output is B, D, E.

With two coordinates, time is $O(v)$ for $v$ visited nonempty nodes, including point tests and report work. It is at least proportional to the number of reported points, and can be $O(n)$ in the worst case. Recursive stack space is $O(h+1)$, plus $O(r)$ output storage for $r$ reported points.

Check your understanding¶

Predict the answer before opening the explanation.

1. At root A’s x=5 split, a query has x interval [5,5] and y interval [0,10]. Which sides may be explored, and does A itself qualify?

2. For the usual shared rectangle, A=(5,4) is outside. Why must the algorithm still visit B’s subtree?

Next: Nearest-neighbour search.