Extract a graph from a scalar field: The Morse Complex

Think of a way to characterize a scalar field contains topological information. Now in such a case, critical points of the functions can be used to define nodes or vertices. To connect one crticial point topologically to another, we need the information of the gradient along a path- the maximal path whose tangent vectors align with the gradient information along the path itself. This way, the Morse Complex gives us a structure that represents the gradient flow behavior and completely encapsulates the topology of level sets of a scalar function. In short, what you will get is called a Morse Complex

Speaking Mathematically

Let $f : M → R$ be a smooth function defined on a 2D manifold, where $\nabla f$ denotes its gradient. A point $x \in M$ is called a critical point if $\nabla f(x) = 0$; otherwise, it is a regular point. A critical point is non-degenerate if its associated Hessian matrix is non-singular. A function $f$ is a Morse function if all of its critical points are nondegenerate and the critical points have distinct function values.

At any regular point x, an integral line is a maximal path whose tangent vectors align with $\nabla f$. f increases along the integral line and each integral line originates and terminates at critical points, namely local minima, local maxima, or saddles.

The stable manifold associated with a local maximum $p$ consists of the point itself and all regular points whose integral lines terminate at $p$. The unstable manifold associated with a local minimum $p$ is the point itself together with all regular points whose integral lines originate at $p$. A Morse function f is a Morse-Smale function if the stable and unstable manifolds intersect transversally. Ascending and descending manifolds are obtained as clusters of integral lines having common origin and destination respectively.

In Morse-Smale functions, the integral lines only connect critical points of different indices. The index of a critical point $p$ is defined by the number of negative eigen values of the hessian matrix at that point.

Each critical point of index $n$ is the origin of a set of integral lines that forms an ascending $d −n$-manifold. Symmetrically, it is the destination of a set of integral lines that forms a descending n-manifold. All ascending and descending manifolds of a Morse-Smale function intersect transversally. Therefore, given two critical points $a$ and $b$, where the index of $a$ is one less than the index of $b$, the intersection of the ascending manifold of $a$ and the descending manifold of $b$ is either empty or a $1$-manifold. The critical points and these $1$ manifolds are called nodes and arcs. The one-skeleton formed by the nodes and arcs forms the combinatorial structure of the MS complex.

The combinatorial structure contains much of the semantic information of $f$ , and is useful for simplification and feature identification. The neighborhood of a node a of an MS complex $\Gamma $ is the set of nodes Na that are connected to a by an arc in $\Gamma$. Assuming transversality, the stable manifolds induce a decomposition of the domain into 2-cells, where local minima and saddles correspond to 0-cells, and the integral lines connecting them define 1-cells. The Morse complex segments the domain into regions where gradient flow behaves coherently.

Computing Morse Complex

A combinatorially correct MS complex is very challenging. These algorithms are memory-intensive and computationally expensive, restricting their use to smaller datasets.

Discrete Morse Theory

Now that we are comfortable with the ideas of morse complex for smooth fields, remeber that many scientific data are only available on unstructured meshes.