9.3 Correctness of criticality graph and zone of influence algorithm.

Theorem 5  

The algorithm labels a lattice point r by criticality p iff $r \in \zeta (p)$.

Proof:

The correctness follows from the definitions and the fact that the algorithm labels all points in a highest value first order. Thus, the algorithm maintains the invariant that at each step, if all points q satisfying $\delta(q) \geq \tau$ have been labeled, these points are precisely the set $\bf {X}_{\delta}^{\geq \tau}$. Since points labeled by a criticality p are in the same connected component of $\bf {X}_{\delta}^{\geq \tau}$ as p, it follows that they are in $O_p (\tau )$. The algorithm maintains the invariant that no other criticality is labeled by p. Each criticality q is thus removed from the priority queue when precisely all vertices of $\bf {X}_{\delta}^{> \delta (q)}$ have been removed from the queue and labeled. If q is adjacent to a vertex labeled by p, then at this point q is made the parent of p and the labeling of the zone of p halts. Thus for any $\epsilon > 0$, q must thus be in the same component of $\bf {X}_{\delta}^{\geq \delta(q) - \epsilon}$ as p, by adjacency. Thus $q \in O_p (\delta(q) - \epsilon )$ and so the algorithm conforms to the definitions of the criticality graph and zones, establishing the result.

In a sense, if we wish to view the evolution of the level sets as threshold is varied, we can view the data points as they are being labeled (employing, of course, the methods of so-called volume imaging).