Proofs: Quadtree

The PR quadtree operations keep the compact invariant and answer window and nearest queries exactly full

This proof shows: correctness, termination.

We use the names of the pseudocode. The root cell is $[0, 2^D)^2$, cells are half-open squares, and points have integer coordinates. For a node $u$ let $S(u)$ be the set of points stored in the leaves below $u$. The invariant (Q) asks: (1) each point of the tree lies in the cell of its leaf and is stored once; (2) each leaf holds at most $B$ points; (3) each internal node has $u.count = |S(u)| > B$, and each leaf has $u.count = |u.points|$; and (4) the children of an internal node of side $s$ are its four quadrants, of side $s/2$.

Lemma 1 (quadrants). For a cell $Z$ of side $s \ge 2$, the four quadrants are disjoint, their union is $Z$, and the quadrant chosen for $p \in Z$ is the one that holds $p$. Proof. On each axis, $[c, c + s)$ is the disjoint union of $[c, c + s/2)$ and $[c + s/2, c + s)$, and the test $p_i \ge c + s/2$ picks the half that holds $p_i$. The product of the halves on the two axes gives the claim. $\square$

Lemma 2 (unit cells). A cell of side 1 holds at most one integer point. Proof. It is $[a, a+1) \times [b, b+1)$ with integers $a, b$, and the only integer point in it is $(a, b)$. $\square$

Search. By Lemma 1 and (Q) part 4, at each internal node the point $p$ lies in exactly one child cell, so exactly one leaf has a cell that holds $p$, and line L1 (and line L12) reaches it in at most $D$ steps, since the side halves at each step. By (Q) part 1, $p$ is stored exactly when it is in that leaf's list.

INSERT. Let $p$ be a point of the root cell that is not stored. Lines L1 to L3 add $p$ to the only leaf whose cell holds it, and add 1 to the count of each node whose subtree now holds $p$, so parts 1 and 3 hold. If $|u.points| \le B$, the loop does not run and (Q) holds.

Otherwise the loop starts with a leaf $u$ that holds $B + 1 \ge 2$ points, all in its cell, while (Q) holds at every other node. By Lemma 2, the side of $u$ is at least 2, so line L5 can make the four quadrants. Line L6 moves each point into the quadrant that holds it (Lemma 1), with counts equal to the list sizes; now $u$ is internal with $u.count = B + 1 > B$, so parts 3 and 4 hold at $u$. The children's lists add up to $B + 1$ points, so at most one child holds more than $B$. If none does, (Q) holds everywhere and the loop stops. If one does, it holds exactly $B + 1$ points, all in its cell, and the loop continues with it in the same situation. The side halves at each pass and is at least 2 at each pass, so after at most $D$ passes the loop stops.

DELETE. Let $p$ be stored, let $u$ be its leaf, and let $v_1, \ldots, v_j$ be the path from the root down to the parent of $u$. After line L13, $p$ is gone and the counts of $u$ and of each $v_i$ are one less, so all counts are correct and parts 1, 2 and 4 hold. Part 3 can fail only at the nodes $v_i$, and only when $v_i.count = B$ now.

Line L14 treats $v_j, v_{j-1}, \ldots$ in turn. Claim: when it reaches $v_i$, (Q) holds at every node except possibly $v_1, \ldots, v_i$, and all counts are correct. This holds for $i = j$. If $v_i.count > B$, then $v_{i'}.count \ge v_i.count > B$ for each $i' < i$, because the count of a node is at least the count of each child, so (Q) holds everywhere and the loop may stop. If $v_i.count \le B$, each child $c$ of $v_i$ has $c.count \le B$; by the claim, part 3 holds at $c$, so $c$ is a leaf. Line L14 gathers the lists of the four leaves, at most $B$ points in total, all in the cell of $v_i$ by part 1 and Lemma 1, into one leaf with the same count. Parts 1 to 4 then hold at $v_i$, and the claim holds for $i - 1$. The loop makes at most $j \le D$ steps.

Uniqueness. Let $\mathcal{T}(Z, S)$ be a tree on a set $S$ of points of the cell $Z$ that satisfies (Q). If $|S| \le B$, part 3 forces a leaf with list $S$. If $|S| > B$, part 3 forces an internal root, part 4 fixes its children as the quadrants $Z_k$, and by part 1 and Lemma 1 the child for $Z_k$ is a tree on $S \cap Z_k$ that satisfies (Q). By induction on the side, it is unique. So the shape depends only on $S$.

RANGE-SEARCH. Let $W = [\ell_x, h_x] \times [\ell_y, h_y]$. Each reported point is stored and is in $W$ by the test of line L10, and the calls follow the tree, so each leaf is reached at most once, and by part 1 no point is reported twice. Let $p \in S \cap W$, with leaf $w$. For each node $v$ on the path from the root to $w$, the cells along the path are nested, so $p$ lies in the cell of $v$ and in $W$; the cell of $v$ meets $W$, and line L9 does not stop the search at $v$. Line L11 calls every child, so the search reaches $w$, and line L10 reports $p$. The calls follow a finite tree, so the search stops.

NEAREST. Write $\delta(u) = \operatorname{dist}(q, \text{cell of } u)$. For each point $p$ below $u$, $p$ is in the cell of $u$, so $\lVert q - p \rVert \ge \delta(u)$. For a child $c$ of $u$, the cell of $c$ is inside the cell of $u$, so $\delta(c) \ge \delta(u)$. Hence the keys extracted at line L18 never decrease: a key inserted at line L21 is at least the key just extracted, and the queue returns the smallest key.

Let $p^*$ be a stored point closest to $q$, and suppose the loop ends with $best$ farther than $p^*$, or with $best$ = none. The tree is not empty, so the root has count at least 1. Call a node processed when it was extracted and passed the test of line L19. The root is inserted at line L16, and each processed internal node inserts all its children with a nonzero count. Let $a$ be the deepest node on the path from the root to the leaf of $p^*$ that was inserted into the queue. If $a$ was processed and is a leaf, line L20 compared $p^*$ with $best$, and $best$ is at least as close as $p^*$ from then on, a contradiction. If $a$ was processed and is internal, its child on the path to $p^*$ has a nonzero count and was inserted, against the choice of $a$. So $a$ was never processed. The loop then ended at line L19 with an extracted key $d \ge \lVert q - best \rVert$, while $a$ was in the queue or was the node just extracted. Since $d$ was the smallest key, $\delta(a) \ge d \ge \lVert q - best \rVert > \lVert q - p^* \rVert \ge \delta(a)$, a contradiction. If $best$ = none at the end, the loop stopped because the queue was empty, so $a$ was processed, and the cases above apply. Hence NEAREST returns a closest stored point. Each node is inserted at most once, so the loop stops. $\blacksquare$