Proofs: Point quadtree

The point quadtree keeps the quadrant invariant and range search reports exactly the points in the box full

This proof shows: correctness, termination.

We use the names of the pseudocode. Write $\text{quad}(p, q) = [q_x \ge p_x] + 2[q_y \ge p_y]$. The invariant (Q) says that for each node $t$ and each point $q$ in the subtree $t.child[i]$, $\text{quad}(t.point, q) = i$, and that no point is stored twice.

Lemma 1 (regions). Define $R(\text{root}) = \mathbb{R}^2$ and, for a node $t$ with point $p$, let $R(t.child[i]) = R(t) \cap Z_i(p)$, where $Z_0(p) = \{x < p_x, y < p_y\}$, $Z_1(p) = \{x \ge p_x, y < p_y\}$, $Z_2(p) = \{x < p_x, y \ge p_y\}$ and $Z_3(p) = \{x \ge p_x, y \ge p_y\}$. If (Q) holds, every point of the subtree of a node $u$ lies in $R(u)$. Proof. By induction on depth: a point $q$ in the subtree $t.child[i]$ lies in the subtree of $t$, so in $R(t)$, and has $\text{quad}(t.point, q) = i$, which means $q \in Z_i(t.point)$. $\square$

Search. If (Q) holds and $p$ is stored at a node $v$, then at each proper ancestor $t$ of $v$, the point $p$ is in the subtree $t.child[i]$ with $i = \text{quad}(t.point, p)$, so the path of INSERT from the root reaches $v$. If $p$ is not stored, the path ends at an empty child. Each step goes one level down, so the walk stops after at most $h$ steps.

INSERT. If the tree is empty, line L1 makes a one-node tree, which satisfies (Q). Otherwise, by the search argument, line L2 stops if $p$ is stored, so no point is stored twice. Each pass of lines L3 to L5 moves one level down, so the loop stops. When line L4 adds $p$ as $t.child[i]$, the nodes whose subtrees change are $t$ and its ancestors, all on the path. At each such node $u$, the loop chose the child $\text{quad}(u.point, p)$, and $p$ is in the subtree of exactly that child; so (Q) holds at $u$. Other nodes do not change.

RANGE-SEARCH. Let $Q = [\ell_x, h_x] \times [\ell_y, h_y]$. Each reported point is stored and lies in $Q$ by line L7, and each node is visited at most once, since the calls follow the tree; with no point stored twice, no point is reported twice. Let $q \in Q$ be stored at a node $v$, and let $t$ be a proper ancestor of $v$, with point $p$, such that $v$ is in the subtree $t.child[i]$. By (Q), $q \in Z_i(p)$. If $q_x < p_x$ then $\ell_x \le q_x < p_x$, so $W$ holds; if $q_x \ge p_x$ then $h_x \ge q_x \ge p_x$, so $E$ holds. In the same way, $q_y < p_y$ gives $S$ and $q_y \ge p_y$ gives $N$. So the two tests that line L9 makes for child $i$ both hold, and the search enters $t.child[i]$. By induction along the path from the root, the search visits $v$, and line L7 reports $q$. The search visits each node at most once, so it stops.

DELETE. If $p$ is not stored, line L10 finds no node, and nothing changes. Otherwise let $t$ be its node. After line L12, the tree holds exactly the stored points other than $p$ and those of $R$, and it satisfies (Q), since removing a subtree removes points from some subtrees and adds none. Each point of $R$ is not in the tree at this moment, so line L13 adds it by INSERT, which keeps (Q) and adds exactly that point. After the loop, the tree holds exactly the old set minus $p$ and satisfies (Q). The loop runs $|R|$ times, so it stops.

Balanced build. Let the points of a group, with distinct $x$ coordinates, be sorted by $(x, y)$, and let $p$ be the point at index $\lfloor m/2 \rfloor$ of a group of $m$. The points before it have $x < p_x$ and go west; the points after it have $x > p_x$ and go east. So the two west quadrants together get $\lfloor m/2 \rfloor$ points and the two east quadrants $\lceil m/2 \rceil - 1 \le \lfloor m/2 \rfloor$ points, and each child group has at most $m/2$ points. Each child gets exactly the points $q$ with $\text{quad}(p, q) = i$, so the tree satisfies (Q), and a node at depth $d$ (root at depth 0) has at most $n / 2^d$ points in its subtree, which gives a height of at most $\lfloor \lg n \rfloor + 1$. $\blacksquare$