Computing and Reducing Slope Complexes

Abstract

In this paper we provide a new characterization of cell decomposition (called slope complex) of a given 2-dimensional continuous surface. Each patch (cell) in the decomposition must satisfy that there exists a monotonic path for any two points in the cell. We prove that any triangulation of such surface is a slope complex and explain how to obtain new slope complexes with a smaller number of slope regions decomposing the surface. We give the minimal number of slope regions by counting certain bounding edges of a triangulation of the surface obtained from its critical points.

1 Introduction

Discrete representations of surfaces in 2.5D like images or digital terrain models are discretizations of 2-dimensional (2D) continuous surfaces. Important properties of such surfaces are their critical points: local minima, maxima and saddle points. These points can be connected by monotonic paths that either go up or go down. These paths delineate surface patches that can be characterized by the property that every pair of points inside such a patch can be connected by a monotonic path: slope regions. Slope regions may be seen as “filling the space between the critical points of the surface” [8]. A planar triangle is an example of a slope region and any triangular mesh subdivides the surface into a set of slope regions. Critical points can appear in many different configurations. Also the subdivision into slope regions may take different arrangements.

In this paper, we explain how to create and reduce slope complexes (decomposition of the given 2D continuous surfaces in slope regions), and we also address the question whether there is a minimal number of slope regions that completely fill the surface between a given set of critical points.

Similar considerations have been published by Edelsbrunner et al.  [3,4,5] with the intention to construct a hierarchy of increasingly coarse Morse complexes. The concept of ‘integral line’ (defined in [3]) has great similarity to the monotonic paths of our approach although we may have less geometric constraints. Specifically, our definition does not need smooth surfaces and monotonic paths do not necessarily follow the steepest slope.

The paper is organized as follows: First we give some basic definitions. We then introduce slope complexes as abstract cellular complexes built by slope regions. We then study the properties of the boundaries of the slope regions and identify particular slope regions, named simple and non-simple triangles, that serve us to construct slope complexes composed only by triangles. We then enumerate the conditions to merge slope regions, the basic process to reduce the number of slopes without affecting the bounding critical points. Finally, we compute the minimum number of slope regions needed to cover the surface given its critical points.

2 Preliminaries

Let us introduce the terminology and main definitions which will be used throughout this paper.

Given a continuous function $g:\mathfrak {R}^2 \mapsto \mathfrak {R}$, a 2-dimensional (2D) continuous surface $S=\{(x,y,z) \in \mathfrak {R}^{3} : z=g(x,y)\}$ can be defined. Given a point $p=(x,y,z)\in S$, we sometime denote g(x, y) by g(p) by abuse of notation.

Definition 1

(local neighborhood). Let $p \in \mathfrak {R}^k$ where $k = 1,2, \ldots$ and $r \in \mathfrak {R}$, with $r > 0$. The local neighborhood of p is a k-dimensional open ball of radius r and center p, denoted by $B_k(p, r)$, that is the set of points $q \in \mathfrak {R}^k$ such that $d(p,q) < r$.

Definition 2

(1-extrema). Let $a,b\in \mathfrak {R}$, with $a<b$. Let $\gamma : [a,b] \rightarrow \mathfrak {R}^2$ be a continuous curve and $t \in [a,b]$. If there exists $\epsilon > 0$ such that $g(\gamma (t))\le g(\gamma (s))$, for every $s \in B_1(t, \epsilon ) \cap [a,b]$, then $\gamma (t)$ is a 1-minimum. Similarly, if there exists $\epsilon > 0$ such that $g(\gamma (t))\ge g(\gamma (s))$, for every $s \in B_1(t, \epsilon ) \cap [a,b]$, then $\gamma (t)$ is a 1-maximum. Finally, $\gamma (t)$ is a 1-extremum if it is a 1-maximum or a 1-minimum.

Definition 3

(monotonic path). Let $a,b\in \mathfrak {R}$, with $a<b$. A monotonic path $\pi : [a,b] \rightarrow \mathfrak {R}^2$ between $p=\gamma (a)$ and $q=\gamma (b)$ is a continuous curve satisfying that there is no $t\in (a,b)$ such that $\gamma (t)$ is a 1-extrema.

A level curve is a particular case of monotonic path.

Definition 4

(level curve). Let $a,b\in \mathfrak {R}$, with $a<b$. A level curve $\gamma : [a,b] \rightarrow \mathfrak {R}^2$ is a continuous function such that there exists a constant $c \in \mathfrak {R}$ where $g(\gamma (t))=c$, for all $t \in [a,b]$.

A monotonic path is either non increasing or non decreasing and, then, it is always bounded by a 1-maximum and a 1-minimum. This allows us to provide monotonic curves (excluding level curves) with a natural orientation (in our illustrations: an arrow from point a to point b means an edge with endpoints a and b such that $g(a)>g(b)$.

Different types of points in S can be described depending on their 2-dimensional local neighborhood.

Definition 5

Let p be a point of $\mathfrak {R}^2$. Three categories for p can be distinguished:

• For a 2-minimum point p there exists $r > 0$ such that $g(p)<g(q),$ for every $q \in B_2(p,r)$.

• For a 2-maximum point p there exists $r > 0$ such that $g(p)>g(q),$ for every $q \in B_2(p,r)$.

• A point p is a saddle point if for all $r>0$ there are two points that cannot be connected by a monotonic path in $B_2(p,r)$.

A 2-extremum is either a 2-minimum or a 2-maximum and a critical point is either a 2-extremum or a saddle point. Critical points are also referred to and denoted as follows: 2-min $\ominus$, 2-max $\oplus$ and saddle $\otimes$.

Observe that two 2-maxima (resp. 2-minima) cannot be connected by a monotonic path. Equivalently, two 1-maxima (resp. 1-minima) cannot be connected by a monotonic path (except for level curves).

Remark 1

In this paper, we exclude plateaus (connected component of points with the same g-value) from the considered surfaces that emerge from the expansion of critical points.

3 Slope Complexes

Roughly speaking, a finite regular CW complex [6] can be seen as a partition, in basic building blocks called cells, of a given topological space X. More concretely, for each k-dimensional cell (k-cell) c in the partition of X, there exists a homeomorphism f (attaching map) from the k-dimensional closed ball to X such that the restriction of f to the interior of the closed ball is a homeomorphism onto the cell c, and the image of the boundary of the closed ball is a homeomorphism onto the union of a finite number of cells of the partition, each having dimension less than k. The closed k-cell $\bar{c}$ is the image of such homeomorphism f.

The CW complexes considered in this paper will be cell decomposition, denoted by K[S], of the 2D continuous surface S, obtained from a continuous function $g:\mathfrak {R}^2 \mapsto \mathfrak {R}$, satisfying that all critical points of the surface are 0-cells.

Observe that only 0-, 1- and 2-cells are permitted in K[S]. From now on, we use equivalently the notions vertex, edge, and region as 0-cell, 1-cell and 2-cell respectively similar to [3]. Finally, observe that the boundary of a 2-cell is a continuous closed curve.

Let us introduce the main concept of our paper, slope regions, which are different to the regions defined in [3].

Definition 6

(slope region). Let K[S] be a cell decomposition of a 2D continuous surface S. A slope region R is a 2-cell in K[S] with the constraint that all pairs of points in $\overline{R}$ are connected by a monotonic path inside $\overline{R}$, where $\overline{R}$ is the closure of R (that is, R together with its boundary).

Definition 7

(slope complex). A cell decomposition K[S] of a 2D continuous surface S is a slope complex if all its 2-cells are slope regions.

Now we describe the boundary of any slope region.

Lemma 1

The boundary of a slope region is composed by either a level curve or two monotonic paths connecting a 1-maximum and a 1-minimum.

Proof

The boundary of the slope region is a continuous closed curve $\gamma :[a,b] \rightarrow \mathfrak {R}^2$, since a slope region is a 2-cell of K[S]. This curve can be a level curve, which is a trivial monotonic path. Alternatively, suppose that the g-values (i.e. the values of g) along the boundary vary. Consider the values of $g(\gamma (t))$, with $t \in [a,b]$. Reasoning now by contradiction, assume that $\gamma (t)$ have two 1-maxima and two 1-minima. Since $\gamma (t)$ is a continuous curve, observe that 1-minima and 1-maxima alternate along $\gamma (t)$. By definition of a slope region, the two 1-maxima are connected by a monotonic path, denoted by $\pi _{max}$, inside the slope region. All points along $\pi _{max}$ have g-values between the two 1-maxima, that is, not below the smallest 1-maximum. The path $\pi _{max}$ splits the slope region into two or more sub-regions. The two 1-minima appear in two different sub-regions and they have smaller g-values than the smallest maximum. By the definition of slope region, there is also a path between the two 1-minima, denoted by $\pi _{min}$, which cross $\pi _{max}$ because the extrema are alternating along $\gamma (t)$. Let us see that $\pi _{min}$ cannot be monotonic. Let $p=\pi _{max} \cap \pi _{min}$. Notice that g(p) is a value greater than or equal to the smallest 1-maximum and the smallest 1-maximum is greater than all the possible g-values between the two 1-minima. It means that the g-values in $\pi _{min}$ first increase from one 1-minimum to g(p) and then the g-values decrease from g(p) to the other 1-minimum. Hence, $\pi _{min}$ is not a monotonic path. Consequently there exists only one local 1-maximum and one local 1-minimum along the boundary of a slope region.    $\square$

The boundary of a slope region R can also be folded such that a part of the boundary lies “inside” the region R. When following the boundary such parts are traversed twice.

Definition 8

(inner and outer boundary point). Let R be a slope region bounded by a continuous closed curve $\gamma :[a,b]\rightarrow \mathfrak {R}^2$. Let $p \in \mathfrak {R}^2$ be a point for which there exists $t \in [a,b]$ such that $\gamma (t)=p$. The point p is an inner point of R if there exists $r>0$ such that $B_2(p,r) \setminus \Gamma \subseteq R$, being $\Gamma =\{\gamma (t): t\in [a,b]\}$.

The outer boundary of R is the set of points of $\Gamma$ that are not inner boundary points.

Observe that the outer boundary of R is a simple continuous closed curve.

The following result characterizes the critical points on the inner boundary of a slope region. They can be 2-extrema but never saddle points.

Lemma 2

The boundary of a slope region R may contain as inner boundary points: a 2-maximum, a 2-minimum, or both simultaneously, but never a saddle point.

Proof

Neither two 2-maxima nor two 2-minima can be connected by a monotonic path, then the first part of the statement is trivial. Now, let us see that a saddle point cannot be an inner boundary point of a slope region. A saddle point is characterized by its local neighborhood. By contradiction, assume that R is a slope region with an inner boundary point x being a saddle point. Consider a small enough r such that $B_2(x,r)\subseteq R$, then, by definition of saddle point, there exists p and q in $B_2(x,r)$ such that there is no monotonic path between them, which is a contradiction with the definition of slope region.    $\square$

Fig. 1.

Prototype of a slope region R.

We finish this section by giving a prototype of a general slope region R. Figure 1a shows all the components that R can have. We use following notation in describing a traversal of a complete boundary: curves with arrows indicate descending orientation in g-values, the boundary segments in which the boundary curve is subdivided are denoted with characters a, b, c, d, e, f and g in counter clockwise orientation around the boundary of R with notations $\hat{\;}$ and $\check{\;}$, where for example $\hat{f}$ denotes that we follow the boundary uphill and $\check{a}$ denotes that we follow the boundary downhill (see Fig. 1d for the intuition of descending, ascending, downhill and uphill).

Following the outer boundary we encounter following monotonic paths: $\check{a}, \hat{c}, \hat{f}$ connecting the up-most (highest g-value) point u with the lowest point l. While the inner boundary includes $\check{b}, \hat{b}, d, e, \hat{g}, \check{g}$. Boundary segments d and e are level curves triggered by the hole $\bullet$ and has no orientation. All inner boundaries are single monotonic paths connecting the outer boundary to the inner boundary points of R which are traversed twice and return to the same outer boundary point where they started. A complete traversal of the boundary of this slope region R is

$$(u, \check{a}, l, \check{b}, \ominus , \hat{b}, l, \hat{c}, h, d, \bullet , e, h, \hat{f}, u, \hat{g}, \oplus , \check{g}).$$

Furthermore, R may encapsulate one or more other slope regions which for R appear as holes. See Fig. 1b in which the boundary of the hole is spotted in the contour plot of a grayscale image (Fig. 1c) with similar configuration as prototype. Figure 1d is the mesh plot, where the height corresponds directly to the intensity (g-value) of the image. The boundary of these holes and its connection d and e to the point h on the outer boundary of R should all be level curves.

The other possible cases of the slope region R may exclude any one of the 2-extrema $\ominus , \oplus$ or the holes $\bullet$. The absence of $\ominus$ will infer that l becomes the 1-minimum of R. Similarly in absence of $\oplus$, u becomes the 1-maximum of R.

The formal proof that this general prototype is always a slope region is left to future work. The idea of the prove is as follows¹: Take two points p and q in R, then $g^{-1}(g(p))$ and $g^{-1}(g(q))$ are level curves inside R. These level curves: either (1) cross the connection between the 2-max the 2-min or one hole to the outer boundary; or (2) connect the two monotonic paths of the outer boundary. Then it is possible to construct a monotonic path from p to q following the level curves inside R and the monotonic paths in the boundary of R.

4 Creating Slope Complexes

In this section we prove that a triangulation of a 2D continuous surface is a slope complex.

A simple triangle is defined as a simply-connected planar region in $\mathfrak {R}^3$ (i.e. a connected region without holes and embedded in a plane not parallel to xz- or yz-plane in $\mathfrak {R}^3$) bounded by three edges (not necessarily straight line segments) connecting three vertices a, b and c. Figure 2 shows the different types of triangles that exist. We distinguish between simple triangles (Fig. 2a) and non-simple triangles (Fig. 2b and c) where two of the three vertices coincide. Observe that the edge from a to b is counted twice in Fig. 2b.

Fig. 2.

Simple and non-simple triangles.

Lemma 3

Simple and non-simple triangles are slope regions.

Proof

Since any (simple or non-simple) triangle T is simply-connected and embedded in a plane, there is a monotonic path connecting any two points in T.

   $\square$

As immediate consequence, next result follows.

Corollary 1

A triangular mesh is a slope complex.

Let us explore the triangular slope regions. First, consider a simple triangle abc in $\mathfrak {R}^3$ with edges being monotonic paths. Assume $g(a) \ge g(b) \ge g(c)$, then we have the three following cases:

• 1. If $g(a)=g(b)=g(c)$, the triangle is a plateau (i.e., all points of the triangle having same g-value).

• 2. If $g(a)=g(b)$ and $g(b)>g(c)$ then, the triangle have one edge with constant g-value, vertices a and b are 1-maxima and vertex c is a 1-minimum. If $g(a)>g(b)$ and $g(b)=g(c)$ we can follow a similar reasoning than above.

• 3. If $g(a)>g(b)>g(c)$ (Fig. 2a), then, vertex a is a 1-maximum and vertex c is a 1-minimum along the boundary of the triangle and vertex b is in-between. Vertex a does not need to be a 2-maximum since other neighbors outside the triangle can be larger. Analogously, vertex c does not need to be a 2-minimum. Vertex b cannot be a 1-maximum or a 1-minimum. If we restrict our vertices to 2-dimensional critical points then b must be a saddle point. We discuss these cases below (Sect. 6.1).

Second, in the non-simple case, the outer boundary (self-loop attached to vertex a) is a level curve surrounding vertex b. Since $g(b) \not = g(a)$ vertex b is an extremum surrounded by level curves with g-values between g(a) and g(b). The edge connecting vertices a and b is a monotonic path. Any point p inside the non-simple triangle must satisfy that $g(p)\in [\min (g(a),g(b)),\max (g(a),g(b))]$ and can be connected to the edge (a, b) following a level curve.

The third type of triangle (Fig. 2c) contains a self-loop attached to vertex a inside the triangle as a level curve. Observe that a sub-complex bounded by the level curve can exist but is not part of the triangle, seen from the triangle it is a hole. In this case $g(a) \not = g(b)$ are the 1-extrema of the triangle and the connections between vertices a and b are monotonic paths. The points in the loop has the same g-value as g(a) and any point of the loop as well as inside the triangle can be connected to vertex b by a monotonic path.

5 Merging of Slope Complexes

In this section we establish conditions to obtain a new slope region as a result of merging two slope regions. The final aim is to start from a slope complex (which can be, for example, a triangular mesh) and produce a new slope complex, homeomorphic to the former, obtained by merging slope regions, decreasing, in this way, the initial number of slope regions of the complex.

Fig. 3.

Merging two slope regions $R_1$ and $R_2$

Let $R_1$ and $R_2$ be two slope regions sharing a common edge (a, b). Since $R_1$ and $R_2$ are slope regions then the edge (a, b) is a level curve or a monotonic path. Without loss of generality, Suppose $g(a)\ge g(b)$. Let $t_1, s_1, t_2, s_2$ denote the 1-maxima and 1-minima of $R_1$ and $R_2$ respectively. Then, the two slope regions $R_1$ and $R_2$ can be merged into a new slope region U, by removing the common edge (a, b) if the following properties are satisfied:

• 1. The common edge is not a self-loop, that is, vertex a is different to vertex b.

• 2. One of the two 1-minima is on the common boundary.

• 3. One of the two 1-maxima is on the common boundary.

Now, let us see that there exists a monotonic path between two any points of U:

• Any pair of points in $R_1$ are connected by a monotonic path because $R_1$ is a slope region. The same is true for $R_2$.

• Any pair of points $r_1 \in R_1$ and $r_2 \in R_2$ with $g(a) \ge g(r_1), g(r_2) \ge g(b)$ can be connected by a level curve to points on the common edge (a, b) which is a level curve or a monotonic path.

• We now consider points outside the range of [g(b), g(a)]. Let us assume that $g(t_1) > g(a)$ (see Fig. 3). Then, clearly, point $t_1$ is not on the common edge (a, b). By requirement 3, point $t_2$ must be on the common edge (a, b). Hence for all points $r_2 \in R_2$, $g(r_2)$ is not higher than $g(t_2)$ and then any point $r_2\in R_2$ can be connected by a monotonic path to point $r_1 \in R_1$ for $g(r_1) > g(t_2)$. The same holds for the case of $g(t_2) > g(a)$ with the roles of $R_1$ and $R_2$ interchanged. Analogously we argue for the 1-minima $s_1$ and $s_2$.

6 On the 1-Skeleton of a Slope Complex

The 1-skeleton of a slope complex K[S] is the graph formed by the vertices and edges of K[S]. Recall that K[S] should contain at least all the critical points of the 2D continuous surface S. Now, in order to provide the minimum number of slope regions that a 2D continuous surface S can be decomposed, we assume that the vertices of K[S] are only the critical vertices of S, i.e., denote by $G=(V,E)$ the 1-skeleton of K[S], then V (the set of vertices of K[S]) coincides with the set of critical points of S, being E the set of edges of K[S]. We also assume that there is only one infinite region called the infinite background. Finally, observe that G is planar. The set of maxima, minima and saddle vertices will be denoted respectively by $V_{\oplus }$, $V_{\ominus }$ and $V_{\otimes }$. The set of edges between the set of vertices will be denoted by $E_{\oplus }$, $E_{\ominus }$ and $E_{\otimes }$, respectively.

In Subsect. 6.1 we explore the induced subgraphs $G_{\otimes }\subset G$ of saddle vertices and in Subsect. 6.2 we consider induced subgraphs $G_{\pm } = G \setminus G_{\otimes } \subseteq G$ of extrema only.

6.1 Forest of Saddles

Adding the constraints given in [3] to the 2D continuous surface S, we can assume that saddle points are vertices of $G=(V,E)$ of degree 4, since saddle points with higher degree can be unfolded into a set of connected saddle points of degree 4 (see [3]). Besides, vertices can be characterized by edges incident to it and their respective orientation: (1) all the edges incident to a saddle point have alternating directions; (2) the in-degree of a maximum is 0; and (3) the out-degree of a minimum is 0.

Remark 2

Every extremum on the boundary of any slope region with more than two vertices is adjacent to a saddle.

By Remark 3, saddle points can be connected but cannot form cycles.

Remark 3

Any connected configuration of saddles $G_{\otimes } = (V_{\otimes }, E_{\otimes }) \subset G$ is acyclic, i.e., they form tree structures.

Therefore the saddle points form a forest.

Lemma 4

Let $G_{\otimes }=(V_{\otimes }, E_{\otimes })$ be the subgraph of G induced by the set of vertices $V_{\otimes }$ and let $T_i$, $i=1,\ldots n$, be the n maximal connected components of $G_{\otimes }$ which are trees by Remark 3. Let $V_{\otimes ,i}, i=1,\ldots n$, be the set of vertices of $T_i$. Let us focus on the edges in $(V_{\otimes ,i} \times V)\cap E$ of the ith connected component of $G_{\otimes }$ and ignore if extrema at the leafs are shared by several trees.

• 1. If the tree $T_i$ contains $|V_{\otimes ,i}|=k_i$ connected saddle points then there are $2(k_i+1)$ pending edges (i.e., edges incident to leafs). The end points of these pending edges are extrema determined by the orientation of the edges. That is, if (s, v) is one of these pending edges then $(s,v) \in V_{\otimes ,i} \times V_{\ominus }$ or $(v,s) \in V_{\oplus } \times V_{\otimes ,i}$.

• 2. Furthermore the pending edges have alternating orientations leading to an alteration of $k_i+1$ minima and $k_i+1$ maxima as leafs when moving around the tree.

• 3. The extrema of a connected component of saddle points are connected by monotonic paths formed by the oriented edges of the internal nodes of the tree.

Proof

We prove the three properties separately.

• 1. Each saddle point of $T_i$ generates four edges in G. Besides, the $k_i$ saddle points are connected by $k_i-1$ edges in the tree. Since each edge is counted twice from each end point we have a total of $4 k_i - 2(k_i-1) = 2k_i+2$ pending edges in each connected component $T_i$. As end points of the pending edges only extrema are available since all saddle points have been collected in the forest and $T_i$ is maximal.

• 2. All the edges of a saddle point have alternating directions in clockwise and counter-clockwise orientation. If two saddle points are connected then adjacent leafs are connected by a monotonic path. Since the connected component of saddle points is supposed to be maximal no saddle point can appear as a leaf. Hence the target of an outgoing edge is a minimum and the start of an outgoing pending edge is a maximum.

• 3. A connected component $T_i$ consists of saddle points inside the tree and of extrema at the leafs. Starting with a maximum we follow the tree downwards keeping the tree always on the same (e.g. left-hand) side. This monotonic path ends in the adjacent minimum. Similarly we can start at a minimum and follow the tree up-wards keeping the tree on the same side. We find the next maximum as end point of a monotonic path.

   $\square$

Figure 4a illustrates the main content of the above lemma by an example.

Fig. 4.

Folding a configuration with four saddles.

Remark 4

Each connected component $T_i$ is connected to $|V_{\otimes ,i}|+1$ maxima and to the same amount of minima in G. Ignoring the sharing of extrema between different components, altogether the saddle points are connected to $|V_{\otimes }|+n$ maxima and to $|V_{\otimes }|+n$ minima in G.

Slope regions are generated by connecting the alternating extrema in the order of the leafs of each saddle tree. Observe that this is not necessarily the smallest number of slope regions decomposing the 2D continuous surface S and extrema may not be connected originally.

Remark 5

This new graph is also denoted by $G=(V,E)$ and its faces generate a slope complex K[S] which is again a cell decomposition of S in slope regions.

6.2 Graph of Extrema

Here we consider the subgraph $G_\pm = (V_\pm , E_\pm )$ of G obtained after the removal of all saddles. Then, $V_\pm = V_\oplus \cup V_\ominus$ and $E_\pm = (V_\oplus \times V_\ominus ) \cap E$.

These graphs of extrema have another interesting property: they form alternating sequences of maxima and minima connecting an extremum to itself along a closed level curve. In contrast to connected saddle components minimax-sequences can form cycles of lengths 2 (double edge), 4 (non-well-formed), 6 and so on.

Cycles of lengths 2 surround slope regions. The regions surrounded by longer cycles do not form slope regions since they contain more than one minimum and more than one maximum by Lemma 1.

The cycle of length 4 corresponds to the well-known checkerboard pattern, the non-well-composed configurations [7]. It “hides” a saddle point inside the cycle (compare with [2]). This is true for all longer cycles of extrema, a cycle of 2n length needs $n-1$ saddle vertices to subdivide the interior region completely into slope regions. The insertion of one additional (saddle) vertex in such non-well-composed configuration with successive triangulation produces a set of slope regions covering the previous non-slope region [2, Sect. 3.1].

We have seen in Lemma 1 that any slope region with n critical points have a 1-maximum and a 1-minimum in its boundary. Consequently the other $n-2$ vertices in its boundary must be saddle points.

6.3 Operations Required to Generate a Minimal Slope Complex

We finish this section with the study of generating a minimal slope complex K[S] which is a decomposition of S in the smallest number of slope regions. Observe that this complex satisfies at least that its vertices are only the critical points of S.

First, after contraction of saddle points in each saddle tree, we only have slope regions formed by two edges connecting a saddle point and another edge connecting two vertices in $V_\pm$. Figure 4b shows the graph where all saddle points are contracted into a single saddle point.

Lemma 5

The number of slope regions remains the same if all edges between saddle points are contracted.

Proof

Edges between saddle points are oriented and, hence, cannot form self-loops, a pre-condition for contraction. The contraction of an edge $(x,y) \in E, x \not = y$, identifies vertices x and y and removes the edge (x, y) from E: The graph after contracting one edge has one less vertex and one less edge. There are no changes in the number of slope regions due to Euler’s number is the same after contracting the edge.    $\square$

Finally, the combination of slope regions formed by two triangles may still be simplified. Let us denote by ±-edge an edge in $E_\pm$.

Fig. 5.

Merging two triangles into one slope region with 4 edges.

Remark 6

Removing the ±-edge shared by two slope regions produces a new slope region.

The dotted edge in Fig. 5 connects the two extrema. By removing the ±-edge we obtain a new slope region. In this way, the total number of slope regions can be reduced.

Remark 7

The total number of slope regions decreases when two slope regions sharing a ±-edge merge.

Observe that if the ±-edge bounds the infinite background or it is in the boundary of exactly one slope region, then it cannot be contracted.

Now, we apply the following operations to a given 1-skeleton G(V, E) obtained from a slope complex K[S] with vertices being the critical points of S, to generate a minimal slope complex $G'(V,E')$ preserving all the vertices of G and having the minimum number of slope regions satisfying the Euler’s formula:

• 1. Contract all edges in $E_{\otimes }$.

• 2. Keep outer ±-edges (i.e., ±-edges in the boundary of the infinite background).

• 3. Keep all inner ±-bridges (i.e., ±-edges in the boundary of exactly one slope region),

• 4. Delete all other inner ±-edges (i.e., ±-edges that are not outer ±-edges and are shared by exactly two slope regions).

Lemma 6

The minimal graph $G'$ is plane, all faces are slope regions and it cannot be further reduced without destroying the property that all faces are slope regions.

Proof

Deletion of an edge does not change the planarity of a graph. We show that the deletion of a ±-edge merges two slope regions into a new region which is a slope region. A ±-edge of the slope complex G of critical points may be on the boundary or may be a ±-bridge or it may be an inner ±-edge of G. In the first two cases the ±-edge bounds a single slope region. Notice that a bridge need not be an outer edge and is therefore separately mentioned. An inner ±-edge in a slope complex is adjacent to two other minimal slope regions each being a slope region with the same two local extrema. Hence the quadrilateral formed after the removal of the ±-edge is also a slope region. This corresponds to the Quadrangle Lemma in [3]. The argument remains true after the first ±-edge of multiple ±-edges is removed. Therefore all multiple ±-edges can be removed and the merged slope regions still share the same two extrema in a single slope region.    $\square$

Finally we proceed to show the given count of slope regions. We have seen that all edges attached to saddle points do not have any influence on the number of slope regions. All edges between two saddle points can be contracted without reducing the number of slope regions and saddle points cannot form cycles.

Remark 8

The total number of slope regions of $G'$ if the graph doesn’t contain any multiple edges or self-loops is:

$$\begin{aligned} |\{ e \in E_{\pm } \;|\; e \, \text {is not an inner}\, \pm \!\text {-edge }| \end{aligned}$$

(1)

Observe that Eq. (1) counts only one slope for outer ±-edges and inner ±-bridges.

7 Conclusions and Future Work

In this paper, we begin with a 2D continuous surface where we define the critical points using local neighborhoods. The surface need not be necessarily piecewise linear or from the smooth category but it should satisfy that critical points are distinct. We then explore the topological properties exhibited by the configuration of given critical points and the space enclosed (slope region) between them. We define slope regions as simply connected components such that any two points in them are connected by a monotonic path. Unlike [3], we allow intersection of monotonic paths and provide a more general topological aspect of the given surface. We show that any 2D continuous surface can be represented as a slope complex and the combinations of different slope regions can be merged to obtain a simplified slope complex. For realization and processing, we use graph-based entities (vertices, edges, and slope regions) similar to [3]. We end the paper by giving the formula to count the minimum number of slope regions required to represent a 2D continuous surface, given the number of critical points.

We started our research on slope regions to better understand the results of our previous work [2] with LBP pyramids where the focus was on critical points. These multiresolution hierarchies of images were built based on a criterion of minimal contrast when merging regions and yields excellent reconstructions with only a very small fraction of image regions. The concept of slope region should enable additional rules to improve the efficiency of our computation.

We know that the partition into slope regions is not unique. What looks as a disadvantage could be used to optimize the receptive field of important critical points and shrink slope regions with “minor importance”. Persistent homology should enable further removal of critical points that are due to noise.

Extensions to higher dimensional spaces would establish an interesting connection to frequently used optimization processes. They seek extrema in the space spanned by objective functions. Iterative optimization approaches could be constrained to slope regions leading to the global optimum.