4.1.1 Axioms.

• Firstly, we assume that (for n-dimensional data) $B (\bf {X}_{f}^{\geq \tau})$ is a finite collection of disjoint, compact, and oriented n-1-manifolds, embedded in $\bf {E}^n$.

• Secondly, let M be a manifold (component of $B (\bf {X}_{f}^{\geq \tau})$) and let C be a d-dimensional hypercube C, $d \leq n$. We assume that each connected component (patch) $\sigma$ of $M \cap C$, is a d-1-dimensional set that is bicontinuously mappable to the d-1-dimensional unit disk, so that the intersection of $\sigma$ with the interior of C is a d-1-dimensional set homeomorphic to $\bf {E}^{d-1}$ and the intersection of $\sigma$ with boundary of C is homeomorphic to the d-2 dimensional sphere, such that $\sigma$ divides C into two components, one of which contains only vertices from a single connected component of Highs with respect to C. Further, the intersection of $B (\bf {X}_{f}^{\geq \tau})$ with any d-dimensional hypercube C divides C into a set of disjoint d-dimensional connected components, with each such component containing precisely the vertices from a single nonempty, connected component (with respect to C) of High vertices, or precisely the vertices from a single connected component of Lows (with respect to C).

• Thirdly, we assume that the relative interior of each component M of $B (\bf {X}_{f}^{\geq \tau})$ contains only a single component of $\bf {X}_{\delta}^{\geq \tau}$ (Highs), and each component of the relative exterior of M contains precisely a single component of the complement of $\bf {X}_{\delta}^{\geq \tau}$ (Lows).

The first and third axioms serve to uniquely define the topology of $B (\bf {X}_{f}^{\geq \tau})$. The third axiom says that the topology of $B (\bf {X}_{f}^{\geq \tau})$ is completely defined by the enclosure of connected components of $\bf {X}_{\delta}^{\geq \tau}$, and is the simplest one that does the job.

The second axiom serves to more precisely specify the geometry of the iso-surfaces. It specifies that the surfaces separate the Highs and Lows in the simplest possible way within any hypercube. It also aids in the proof of the main result of this section. One can demonstrate that axiom 3 is implied by axiom 1 and 2. We include axiom 3 because this seems to reflect the major goal of iso-surface construction from a global perspective. But the fact that axioms 1 and 2 are sufficient has important implications. It says that the manifolds (iso-surfaces) can be constructed locally within each hypercube. We use this fact to demonstrate the existence of manifolds satisfying the axioms via an efficient, simple, dimension-independent, and completely parallelizable iso-surface construction algorithm called SpiderWeb, in the section on algorithmic issues.

Let f and f' interpolate $\delta$ and satisfy the axioms.

Lemma 1   $\bf {X}_{f}^{\geq \tau}$ and $\bf {X}_{f'}^{\geq \tau}$ have the same number of components.

Proof: Let f interpolate $\delta$ and satisfy the axioms. Now the relative interiors of the boundary manifolds of $B (\bf {X}_{f}^{\geq \tau})$ consist of some number k of disjoint components. $\bf {X}_{f}^{\geq \tau}$ is the closure of these k components, and thus consists of the union of these components with $B (\bf {X}_{f}^{\geq \tau})$. Since by axiom 1, the boundary manifolds of $B (\bf {X}_{f}^{\geq \tau})$ are pairwise disjoint, $\bf {X}_{f}^{\geq \tau}$ must also consists of k components. Since, by axiom 3, each of these k components contains a single component of $\bf {X}_{\delta}^{\geq \tau}$ it follows that the number of components of $\bf {X}_{\delta}^{\geq \tau}$ is also k. Since this is true for any function satisfying the axioms, it follows that $\bf {X}_{f}^{\geq \tau}$ and $\bf {X}_{f'}^{\geq \tau}$ both consist of k components.

Lemma 2  

Let e be a hypercube edge. Then e has a single intersection point with $B (\bf {X}_{f}^{\geq \tau})$ (hit point) if and only if the incident endpoints are High and Low, respectively.

Proof:

This follows immediately from axioms 1 and 2.

Lemma 3  

Each 2-dimensional hypercube face (square) F has 0, 2 or 4 hit points.

Proof:

This follows from a simple parity argument; or by examining the 4 possible arrangements of Highs and Lows on the 4 vertices: 1, 2 or 3 edge adjacent Highs give 2 hits, and a pair of diagonally opposite Highs give 4 hits (see figure 3).

Definition 16  

Two hits are adjacent in face F if they are connected by a curve segment of $B (\bf {X}_{f}^{\geq \tau}) \cap F$. Connectivity of sets of hits is defined by the transitive closure of adjacency. Connected components are defined accordingly.

Lemma 4  

Each hit point h of face F is connected by a curve segment of $B (\bf {X}_{f}^{\geq \tau}) \cap F$ to a unique (adjacent) hit point h' in F.

Proof:

This result follows from the previous lemma, the disambiguation rule, and axiom 2 (see figure 3).

In what follows, let f and f' interpolate $\delta$ and satisfy the three axioms.

Definition 17  

We can identify a hit (uniquely) by the hypercube edge on which it occurs. Below when we wish to refer to the actual hit point (and not merely the edge) we will indicate this fact.

Lemma 5   $B (\bf {X}_{f}^{\geq \tau})$ and $B (\bf {X}_{f'}^{\geq \tau})$ have the same hit sets (as edge sets).

Proof:

This follows from lemma 2. Changing the interpolation function does not change whether a vertex is High or Low.

Definition 18  

Two surface patches are adjacent if they intersect.

Lemma 6   Two d-1 dimensional surface patches of M, $\sigma \in C$ and $\sigma' \in C'$, are adjacent if and only if their intersection is a set of d-2 dimensional surface patches of M in the d-1 dimensional boundary hypercube shared by C and C'. Further, if $\sigma$ and $\sigma'$ are adjacent then they share at least one hit point in each component of their intersection.

Proof: This follows immediately from the axioms, and the fact that the d-1-dimensional boundary hypercube is completely shared by C and C'. The fact that they share a hit point in each component of their intersection is due to the fact that their intersection must occur on at least one cube edge, and thus they share this hit.

Lemma 7   Each connected component of hits of hypercube C is a member of a unique surface patch $\sigma \in B (\bf {X}_{f}^{\geq \tau}) \cap C$, and conversely the hits contained in each surface patch $\sigma \in B (\bf {X}_{f}^{\geq \tau}) \cap C$ form a unique connected component of hits of C.

Proof: By the definitions of hit point adjacency and connectivity, each pair of hits in a connected component of hits within C is connected by a path within $B (\bf {X}_{f}^{\geq \tau}) \cap C$, and by path connectivity of surface patches, this path must be part of the same patch. Thus the connected set of hits all lie in a single patch $\sigma$ of C.

For the other direction, we must show that the hit points of $\sigma$ form a connected set within C. The proof is by induction on the dimension d. The result is clearly true for d=1 and d=2, by lemmas 2 and 4 respectively. For the inductive hypothesis, we assume that for all $j \leq d-1$, the hits of each patch of a j-dimensional hypercube C is a connected set, within C. For the inductive step let $\sigma$ be a patch of a d-dimensional hypercube C. From axiom 2, we know that the intersection, $\beta$, of $\sigma$ with the boundary of C is homeomorphic to a d-2 dimensional sphere, and thus path connected. Let h and h' be any two hit points of $\sigma$. Then there is a path $\pi \in \beta$ from h₁ to h₂. This path $\pi$ passes through a sequence, $\sigma_1 , \ldots , \sigma_m$, of adjacent d-2-dimensional patches in the d-1-dimensional boundary hypercubes of C. For each $1 \leq i < m$, let h_i be any hit point in $\sigma_i$ and let h_i+1 be any hit point in $\sigma_{i+1}$. We claim h_i and h_i+1 are part of the same component of hits of C. Since $\sigma_i$ and $\sigma_{i+1}$ are adjacent, then they by lemma 7 and the induction hypothesis, they share at least one hit point in common. Also, by the induction hypothesis, the hits of $\sigma_i$ and $\sigma_{i+1}$ are each connected sets of hits, within their respective boundary hypercubes, and thus the union of the hits of $\sigma_i$ and $\sigma_{i+1}$, must be part of the same connected set of hits in C. Thus h_i and h_i+1 are part of the same component of hits in C. Since $h \in \sigma_1$ and $h' \in \sigma_m$, this gives the result.

Lemma 8   Each connected component of hits is contained in a unique component manifold M of $B (\bf {X}_{f}^{\geq \tau})$, and conversely the hits contained in each such manifold M form a unique connected component of hits.

Proof: A connected component of hits is contained in a single manifold M by the definition of hit adjacency and the connectivity of M. This manifold is unique, since by axiom 1 the manifolds are pairwise disjoint.

For the other direction suppose that M contains two hits h₁ and h₂. There is clearly a path $\pi$ in M from h₁ to h₂. This path passes through some sequence of patches of M, $\sigma_1 , \ldots , \sigma_m$, of cubes $C_1, \ldots , C_m$, where $h_1 \in \sigma_1$ and $h_2 \in \sigma_m$. For each $1 \leq i < m$, $\sigma_i$ contains a unique connected component of hits within C_i, by lemma 7. For each such i, $\sigma_i$ and $\sigma_{i+1}$ intersect in in a shared boundary hypercube C'_i of C_i and C_i+1, from lemma 6. Also from lemma 6, we know that $\sigma_i$ and $\sigma_{i+1}$ share at least one hit point in C'_i. It follows that hit points of $\sigma_i$ and $\sigma_{i+1}$ are part of the same connected component of hits. Thus h₁ and h₂ are part of the same connected component of hits.

From lemma 8 we immediately get.

Lemma 9   $B (\bf {X}_{f}^{\geq \tau})$ and $B (\bf {X}_{f'}^{\geq \tau})$ consist of the same number of components.

Let H be a connected component of hits (edges). Let M be the component of $B (\bf {X}_{f}^{\geq \tau})$ containing H and let M' be the component of $B (\bf {X}_{f'}^{\geq \tau})$ containing H.

Lemma 10   Let M consist of patches $\Sigma = \sigma_1 , \ldots , \sigma_k$. Then there exists a one-to-one mapping $\iota$ of $\Sigma$ onto the patches of M' so that for all $1 \leq i < j \leq k$, $\sigma_i$ is adjacent to $\sigma_j$ if and only if $\iota ( \sigma_i )$ is adjacent to $\iota ( \sigma_j )$. In addition, their respective intersections have the same number of components.

Proof: The mapping $\iota$ associates two patches if they share the same hit set (as edges). This mapping is one to one and onto by lemma 7.

If $\sigma_i$ is adjacent to $\sigma_j$, then from the above lemmas, they share at least one hit in common (on edge e), for each component of their intersection. Then $\iota ( \sigma_i )$ and $\iota ( \sigma_j )$ also share a hit on edge e and are thus also adjacent. It is easy to see that the converse holds.

In other words if we represent the patches and their adjacencies by graphs in the natural way, then the graphs representing M and M' are isomorphic.

Using the above facts we can prove:

Lemma 11  

M and M' are homeomorphic.

Proof:

We can construct a global homeomorphism from M to M' piecewise via their patches. From axiom 2, both patches $\sigma_i$ and $\iota ( \sigma_i )$ are bicontinuously mappable to the unit disk. From lemma 10 and lemma 7, we know that $\sigma_i$ is adjacent to $\sigma_j$ if and only if $\iota ( \sigma_i )$ is adjacent to $\iota ( \sigma_j )$, and from lemma 6 and from axiom 2 we know that the intersections of the corresponding pairs of adjacent patches are also bicontinuously mappable. We can thus bicontinuously map $\sigma_i$ to $\iota ( \sigma_i )$ in a manner that extends to a bicontinuous mapping of $\sigma_j$ to $\iota ( \sigma_j )$, for each such adjacent patch. Thus we can define the homeomorphism iteratively on each $\sigma_i$ in a manner that produces a global homeomorphism from M to M', giving the result.

It is only the location of the manifolds M and M' within a given cube that can differ. They pass through precisely the same cubes in precisely the same way.

We can now prove our main result.

Topological equivalence of Digital Morse interpolants.

Theorem 1  

If f and f' interpolate $\delta$ and satisfy the three axioms, then $B (\bf {X}_{f}^{\geq \tau})$ and $B (\bf {X}_{f'}^{\geq \tau})$ are homeomorphic.

Proof:

Each component M of $B (\bf {X}_{f}^{\geq \tau})$ corresponds to a unique component M' of $B (\bf {X}_{f'}^{\geq \tau})$, by lemma 8. From lemma 11, we know that M and M' are homeomorphic.

The axioms further define the surfaces up to precise geometry, as the location of the surfaces is determined up to the sampling distances. In fact, in some cases we determine several distinct surface patches within a given hypercube, e.g., up to 4 in 3 dimensions.

We can now apply the insights gained from Morse Theory to this discrete digital setting. The question becomes, subject to these assumptions, what are the critical values and associated critical points at which we get topological change in $B(\bf {X}_{f}^{\geq \tau})$? That is the subject of our next section.