The dual surface

Let $M=(E,s,\rho)$ be a discrete surface. The dual surface for $M$ is then the discrete surface

$M^*=(E, s^{-1}\circ \rho, \rho)$.

Thus $M^*$ has the same set $E$ of oriented edges as $M$. Also the reversal  $\rho$ of edges is the same. The faces of $M^*$ are the cycles of $s^{-1} \circ \rho=\rho \circ(s \circ \rho)^{-1}\circ \rho^{-1}$, which means they are the images under $\rho$ of the vertices of $M$. The vertices of $M^*$ are the cycles of $s^{-1} \circ \rho \circ \rho=s^{-1}$ and therefore are the faces of $M$. To say it briefly: $M^*$ is a surface where the vertices and faces of $M$ have interchanged roles.

To draw $M^*$ one can draw a new (“dual”) vertex in the middle of every face of $M$ and connect dual vertices whenever the corresponding faces of $M$ are adjacent.

For every oriented edge $e$ we can draw an arrow from the center of face $\textrm{left}(e)$ to the center of face $\textrm{right}(e)$. So we rotate the arrow  representing an oriented edge of $M$ in a clockwise fashion to draw the corresponding edge of $M^*$. We think of this as just another graphical representation for the same oriented edge $e$.

A number written on an oriented edge can mean two different things: First, it could describe the value of a 1-form  $\omega$ on $e$. For example, in case $\omega=df$ the number signals the difference of function values of $f$ at the end points. Second, it could describe the value of a dual 1-form  $\eta$ on $e$. For example, it could stand for the difference of the values of a dual o-form on the two sides of $e$. It is clear that such a dual 0-form can also be seen as a 0-form on the dual surface $M^*$, justifying our notation $\Omega_0(M^*)$. The same holds for $\Omega_1(M^*)$.

The dual 1-form of a path

To each path $\gamma = (e_1, \ldots ,e_n)$ we can associate a dual 1-form $\hat{\gamma}$ given by

$\hat{\gamma}(e) =\#\{k\in \{1,\ldots,n\} \,|\,  e=e_k\}-\#\{k\in \{1,\ldots,n\} \,|\,  e=\rho(e_k)\}$.

Here are two examples: The following path $\gamma$ passes through one edge $e_2=e_9$ twice:

The corresponding dual 1-form $\hat{\gamma}$ has evaluates to 2 on this edge.

The second example contains the edges $e_2$ and $e_8=\rho(e_2)$.

In the corresponding dual 1-form these two edges cancel:

Let us calculate the derivative of the dual 1-form $\hat{\gamma}$ associated to a path $\gamma$:

d\hat{\gamma}(v) &= \sum_{e\in v} \hat{\gamma}(e)\\
&=\sum_{e\in v} (\#\{k\in \{1,\ldots,n\} \,|\,  e=e_k\}-\#\{k\in \{1,\ldots,n\} \,|\,  e=\rho(e_k)\})\\
&=\#\{k\in \{1,\ldots,n\} \,|\,  \textrm{end}(e_k)=v\}-\#\{k\in \{1,\ldots,n\} \,|\,  \textrm{start}(e_k)=v\}.

If $\gamma$ is closed, this will be zero for all vertices $v$. This is because a closed path enters any vertex as often  as it leaves it. On the other hand, if $\gamma$ is not closed, the $d\hat{\gamma}$ evaluates to $1$ on the vertex $\textrm{end}(\gamma)$ to $-1$ on $\textrm{start}(\gamma)$ and to zero on all other vertices.

In particular this implies that for a closed path $\gamma$ the dual 1-form $\hat{\gamma}$ is also closed, i.e. $\partial \hat{\gamma}=0$.

The derivative of a 1-form

For a discrete 1-form $\omega$ we define a discrete 2-form $d\omega$, called the derivative of $\omega$:

$\displaystyle d\omega(\varphi) = \int_\varphi d\omega :=  \sum_{e \in \varphi}\omega(e)$.

The picture below illustrates this.

Recall that a 1-form $\omega$ is called exact if it is the derivative of some 0-form. $\omega$ is called closed if $d\omega =0$. It is easy to see that exact 1-forms are always closed:


Now that we have two maps called $d$, we sometimes distinguish them by an index. Thus

$d_0: \Omega_0(M) \rightarrow \Omega_1(M)$

$d_1: \Omega_1(M) \rightarrow \Omega_2(M)$

$d_1 \circ d_0 =0$.

The derivative of dual 0-forms provides us with a linear map

$\partial_2 : \Omega_2(M)^*=\Omega_0(M^*)\rightarrow \Omega_1(M^*)=\Omega_1(M)^*$.

Our definitions imply that $\partial_2$ is the adjoint of $d_1$:

\langle\partial f, \omega \rangle &= \sum_{e \in \hat{E}} \partial f(e) \, \omega(e) \\
&=\frac{1}{2}\sum_{e \in E} \partial f(e) \, \omega(e) \\
&=\frac{1}{2}\sum_{e \in E} (f(\textrm{left}(e))-f(\textrm{right}(e))) \, \omega(e) \\
&=\frac{1}{2}\sum_{e \in E} (f(\textrm{left}(e))-f(\textrm{left}(\rho(e)))) \, \omega(e) \\
&=\frac{1}{2}\left(\sum_{e \in E} f(\textrm{left}(e))\omega(e) -\sum_{e \in E}f(\textrm{left}(\rho(e))) \, \omega(e) \right)\\
&= \frac{1}{2}\left(\sum_{e \in E} f(\textrm{left}(e))\omega(e) -\sum_{e \in E}f(\textrm{left}(e) \, \omega(\rho(e)) \right)\\
&=\sum_{e \in E} f(\textrm{left}(e)) \omega(e)\\
&=\sum_{\varphi \in F} \sum_{e \in \varphi}f(\textrm{left}(e)) \omega(e) \\
&=\sum_{\varphi \in F} f(\varphi) \sum_{e \in \varphi}\omega(e) \\
&=\sum_{\varphi \in F}f(\varphi)d\omega(\varphi)\\
&=\langle f, d\omega \rangle.

Dual 1-forms and derivatives of dual 0-forms

The derivative of a 0-form is a function on oriented edges $e$ that records the difference between the values of $f$ at the vertices $\textrm{end}(e)$ and $\textrm{start}(e)$. Similarly, the derivative of a dual 0-form $f$ encodes the difference between the two function values of $f$ on the two sides of $e$: For $f \in \Omega_0(M^*)$ we define

$\partial_2 f: E \rightarrow \mathbb{R}$

$\partial_2 f(e) = f(\textrm{left}(e))-f(\textrm{right}(e))$.

We use the same letters for dual 0-forms and 0-forms, but it will be convenient to use a diffrent letter (pronounced “del”) for the derivative. Formally, $\partial_2 f$ looks like a 1-form, but the meaning is different. So we decide to call an object like the above $\partial_2 f$ a dual 1-form and denote the space of all dual 1-forms by

$\Omega_1(M^*) = \{\eta : E\rightarrow  \mathbb{R} \,|\, \eta\circ\rho = -\eta\}$.

Just as we interpreted $\Omega_0(M^*)$ as the dual space of $\Omega_2(M)$ we can define a non-degenerate pairing between dual 1-forms and 1-forms:

$\langle \,,\rangle: \Omega_1(M^*) \times \Omega_1(M) \rightarrow \mathbb{R}$

$\displaystyle\langle \eta,\omega \rangle :=\sum_{e \in \hat{E}}\, \eta(e)\,\omega(e)$.

Just as we did for 1-forms, we can visualize dual 1-forms by writing numbers on arrows. Also here we could reverse any arrow and change the sign of the corresponding number. The picture below shows the derivative of the dual function that is 1 on the red face and -1 on the blue one.

2-forms and dual 0-forms

Functions on a manifold cannot be integrated per se. This is also the reason for the notation

$\displaystyle \int_U f \, dx_1 \ldots dx_n$

if one wants to integrate a function $f$ over a region $U\subset \mathbb{R }^n$. If you express $f$ in different coordinates  (for example polar coordinates) the integral changes (unless you stick in some Jacobi determinant). Objects living on regions in $\mathbb{R }^n$ that can be integrated independent of the choice of coordinates are called $n$-forms. In the above formula $dx_1 \ldots dx_1$ is such an $n$-form and its integral over $U\subset \mathbb{R }^n$ always calculates the n-dimensional volume of $U$, no matter which coordinates you use. Conversely, if you know the integral of an n-form over any subregion of $U$ you know the $n$-form.

This gives us a clue how to define 2-forms on our discrete surfaces: A 2-form $\sigma$ assigns to each face $\varphi$ a real number $\sigma(\varphi)$. We also use the notation

$\displaystyle \sigma(\varphi) =: \int_\varphi \sigma$.

If $U \subset F$ is a union of faces we define

$\displaystyle \int_U \sigma := \sum_{\varphi \in U} \, \int_\varphi \sigma$.

Also we write

$\displaystyle \int_M \sigma := \displaystyle \int_F \sigma$.

In many situations it is possible to an area to each face. Such an assignment of areas to faces is a special case of a 2-form, usually referred to as the volume form $\sigma_\textrm{vol}$ of $M$. The total area of $M$ is then

$\displaystyle \textrm{vol}(M):=\int_M \sigma_\textrm{vol}$.

Even in the presence of a volume form discrete functions $f \in \Omega_0(M)$ cannot be integrated. This is because they represent function values at vertices and there is no canonical way to multiply such an $f$ with $\sigma_\textrm{vol}$ in order to get a 2-form that can be intergrated.

We use this as a motivation to introduce another kind of objects: dual 0-forms. We think of them as real-valued functions on the surface that are constant on the interior of all faces. Formally speaking they are also just defined as functions

$f: F \rightarrow \mathbb{R}$.

The above remarks should have made it clear though that it is not wise to confuse dual 0-forms with 2-forms: functions cannot be integrated while this is perfectly possible for 2-forms. Functions can however be multiplied with 2-forms, the result being another 2-form:

$\displaystyle \int_\varphi (f\sigma) := f(\varphi) \int_\varphi \sigma$.

Note that this seems to be a reasonable formula for functions $f$ that are constant on each face.

We denote the vector space of all functions by $\Omega_0(M^*)$. This space is indeed canonically isomorphic to the dual vector space of $\Omega_1(M)$: To verify this statement it enough to exhibit a nondegenerate bilinear pairing

$\langle \,,\rangle: \Omega_0(M^*) \times \Omega_2(M) \rightarrow \mathbb{R}$

$\displaystyle\langle f,\sigma\rangle := \int_M f \sigma$.

Finally: If we are given a volume form, we can integrate dual functions by defining

$\displaystyle \int_M f :=  \int_M f \, \sigma_\textrm{vol}$.

Integral of dual functions over unions $U$ of faces can then be defined in a similar way.

Implementation issues

Instead of describing faces as subsets $\varphi \subset E$, it is sometimes more convenient to choose for each face $\varphi$ an edge $e_\varphi \in \varphi$ and work with the set

$\hat{F}=\{e_\varphi \, | \, \varphi \in F \}\subset E$.

Knowing $e_\varphi$ we can easily recover the other edges that make up the face $\varphi$ by applying $s$ repeatedly to $e_\varphi$.

Similarly, we can choose an outgoing edge for each vertex, a particular orientation for each unoriented edge and work with sets of edges $\hat{V}$ and $\hat{E}$ that are in one-to-one correspondence with $V$ and $E$.

Working with $\hat{E}$, $\hat{F}$ and $\hat{V}$ instead of $E$, $F$ and $V$ can be important for efficient computer implementations. As we will see, it is sometimes also useful for theoretical purposes.

Locally constant functions

Let $f$ be a discrete function on $M$ whose derivative vanishes. For any two points $i$ and $j$ in the same connected component we have a path $\gamma$ from $i$ to $j$ and

$\displaystyle f(j)-f(i) = \int_\gamma df = 0$

Thus $f$ is constant on each connected component. Conversely, we can choose different constants $c_1, \ldots, c_k$ corresponding to the various connected components $M_1, \ldots, M_k$ of $M$ and define a function $f$ that assumes the value $c_\alpha$ on all vertices in $M_\alpha$. Such a function is called locally constant and  has zero derivative. Thus the kernel

$H^0(M) := \ker d$

of the linear map

$d: \Omega_0(M) \rightarrow  \Omega_1(M)$

consists of the locally constant functions. Its dimension

$\beta_0(M):= \dim \ker d$

is also called the zeroth betti number of $M$ and equals the number of connected components of $M$.

Discrete 1-forms

What kind of an object is the derivative $df$ of a discrete function? It is a map

$\omega: E \rightarrow \mathbb{R}$

such that

$\omega \circ \rho = -\omega$.

We call such an $\omega$ a discrete 1-form and denote the vector space of all discrete 1-forms by $\Omega_1(M)$. Discrete functions are also called 0-forms on $M$ and the space of all 0-forms is denoted by $\Omega_0(M)$.

We want to ask which 1-forms $\omega$ are of the form $df$ for some discrete function $f$. If this is the case, $f$ is called a primitive of $\omega$ and $\omega$ is called exact. This means we want to know the image of the linear map

$d: \Omega_0(M) \rightarrow \Omega_1(M)$.

This sounds similar to a problem studied in any introductory calculus course: Given a vector field on some open set $U \subset \mathbb{R}^n$, determine whether it is the gradient of a function $f: U \rightarrow \mathbb{R}$. We will procede in the discrete case in a way that hopefully will make clear that even the statements and proofs are very similar in the discrete case to the smooth setting.

If $\gamma = (e_1, \ldots , e_m)$ is a path in $M$ and $\omega \in \Omega_1(M)$ then we define

$\displaystyle \int_\gamma \omega := \sum_{k=1}^m \omega(e_k)$.

We define

$\textrm{start}(\gamma):= \textrm{start}(e_1)$

$\textrm{end}(\gamma):= \textrm{end}(e_m)$.

A nice analogue of the fundamental theorem of calculus is then the (easy to prove) statement

$\displaystyle \int_\gamma df = f(\textrm{end}(\gamma))-(f(\textrm{start}(\gamma))$.

A path $\gamma$ is called closed if

$\textrm{end}(\gamma) =\textrm{start}(\gamma)$.

Thus a necessary condition for $\omega$ to be exact is that

$\displaystyle \int_\gamma \omega =0$

for every closed path $\gamma$ in $M$. This condition is in fact also sufficient:

Theorem: A 1-form $\omega$ on $M$ is exact if and only if the integral of $\omega$ over any closed path $\gamma$ in $M$ vanishes.

Proof: Assume the integral of $\omega$ over any closed path $\gamma$ vanishes. Choose a vertex $i \in V$ and define $f(i)=0$. For any vertex $j$ in the same connected component as $i$ choose a path $\gamma_j$ from $i$ to $j$ and define

$\displaystyle f(j):=\int_{\gamma_j} \omega$.

We claim that this definition is in fact independent of the choice of $\gamma_j$. If $\tilde{\gamma} = (\tilde{e}_1, \ldots, \tilde{e}_\tilde{m})$ is another path from $i$ to $j$ then

$\gamma := (e_1, \ldots ,e_m, \rho(\tilde{e}_{\tilde{m}}), \ldots \rho(\tilde{e}_1))$

is closed and therefore

$\displaystyle 0 = \int_{\gamma} \omega = \int_{\gamma_j} \omega – \int_{\tilde{\gamma}} \omega$.

Now we can show $df = \omega$, at least on the connected component of the vertex $i$: Let $e$ be an edge in this component and choose a path $\gamma = (e_1,\ldots ,e_m)$ from $i$ to $\textrm{start}(e)$. Then $\tilde{\gamma}=(e_1, \ldots ,e_m, e)$ is a path from $i$ to $\textrm{end}(e)$ and

$\displaystyle df(e) = f(\textrm{end}(e)-\textrm{start}(e)=\int_{\tilde{\gamma}}\omega -\int_\gamma \omega = \omega(e)$.

Repeating this construction on all connected components of $M$ we get the desired primitive $f$ of $\omega$ on the whole of $M$.


Discrete functions and their derivatives

A discrete function $f$ on a discrete surface is just a map

$f: V \rightarrow \mathbb{R}$.

The derivative of $f$ is the function

$df: E \rightarrow \mathbb{R}$

$df(e) = f(\textrm{end}(e))-f(\textrm{start}(e))$.

$df$ has the property

$df \circ \rho = -df$

One way to visualize simple functions is to write $f(v)$ on every vertex $v$ where $f(v)\neq 0$. To visualize the derivative one can choose for each unoriented edge $\epsilon$ on which $df$ does not vanish that oriented edge $e \in \epsilon$ for which $df(e) >0$. Then one can draw $e$ as an arrow and indicate the “strength” of $df$ on $e$ by writing the number $df(e)$ on the arrow. Of course one could also choose for every $\epsilon$ an arbitrary orientation $e \in \epsilon$, draw the arrow and indicate $df(e)$ by writing the (now possibleý negative) number $df(e)$ on the arrow. The above convention has the advantage that the resulting picture almost looks like the gradient vector field of a smooth function on a smooth surface.

Paths and connectivity

A path in $M$ from a vertex $i$ to a vertex $j$ is a finite sequence $(e_1, \ldots ,e_m)$ of oriented edges such that

$\textrm{end}(e_k) = \textrm{start}(e_{k+1})$

and $\textrm{start}(e_{1})=i$, $\textrm{end}(e_m) =j$.

A surface is called connected if for any two vertices $i,j \in V$ there is a path from $i$ to $j$. If a surface $M$ is not connected, it is not difficult to see that it nevertheless can uniquely be represented as the disjoint union of several connected surfaces (called the connected components of $M$). Usually we will assume that the surfaces we work with are connected.