1. ABSTRACT.

We propose a new way to organize (typically density based) interpolated geometry in sampled data, such as traditionally rendered for imaging by volume and surface technologies. It is based on an adaptation of Morse theory using combinatorial methods, for the discrete domain, and thus is naturally related to digital topology. The heart and soul of this new thinking is the recognition and cataloging (indexing) of the level set changing criticalities, as the threshold is varied, into a hierarchical criticality graph, with associated zones. In this way all of the discrete data space, in n-dimensions, can be consistently organized. The methods work without any assumption that the underlying function is Morse, in the traditional sense. Using our combinatorial approach, we completely characterize all critical points and structures in multi-dimensional sampled functions. We give an efficient algorithm for computing the criticality graph and zones. We demonstrate that the criticality graph and associated zones have a number of important properties, including the following: Each zone $\zeta$ has an associated real interval $(\tau_1 , \tau_2 ]$. Each level set boundary iso-surface (at any threshold) is completely contained within a zone. A zone $\zeta$ contains an iso-surface if and only if the iso-value x satisfies $\tau_1 < x \leq \tau_2$. Moreover, for any pair of values $\tau_1 < x_1 < x_2 \leq \tau_2$, the iso-surfaces within $\zeta$ for iso-values x₁ and x₂ are topologically equivalent (homeomorphic). We suggest how these properties may be used in a variety of important applications.