9.2.1 Criticality graph and zone labeling algorithm.

Phase 1

One passes the data lattice (including disambiguation points) and identifies (by breadth first search) each degenerate set S. Then one examines the neighbors of each such set S to determine if it is a critical set (of types 5 through 7).

For each point that is not part of a critical set, one determines if it is a point criticality of types 1 through 4, by examining all neighboring points.

Phase 2

One begins the labeling of zones from the criticalities. One maintains a priority queue (max-heap for efficiency) on $\delta(p)$, with priority given to critical points to break ties. One labels each critical point (or critical set) p as part of its own zone, that is, assigns l(p) = p, and places the point on the heap. For critical sets, we choose an arbitrary point in the set for the label, and only place the boundary points of the set on the heap. One then iterates the following step until a criticality is selected.

Remove a maximally valued r (with label l(r) = p) from the heap. Examine the neighbors of r. If a neighbor q of r is unlabeled and has value less than or equal to critical value f(p), then assign l(q) = l(r) (label q by p) and place q on the heap.

This highest valued first labeling continues until a point q is removed from the the heap so that q is a critical point or part of a critical set. Examine the neighbors of q. For each neighbor r of q that is labeled by a different criticality $p \neq q$, so that l(r) = p, make q the parent of p. At this point all points on the heap with label p are relabeled by q and the algorithm iterates as above.