The discrete Gauss-Bonnet theorem

This is a slight extension of my previous note on discrete Gauss-Bonnet theorem. As mentioned in that note, this is a generalization of the well-known fact that the sum of the exterior angles of a polygon is always {{2\pi}}, which can also be regarded as a very special case of the Gauss-Bonnet theorem.

First of all we introduce a discrete version of surfaces. Let { M} be a ({2}-dimensional) “discrete surface” (here for examples) or a simplicial surface (with or without boundary), which for simplicity is assumed to be contained in {\mathbb R^n}. A discrete surface consists of finitely many “triangles” gluing along their edges. Each triangle is isometric to an ordinary planar triangle on {\mathbb R^2}. We call each triangle a “face”. For each face, there are exactly three edges. And for each edge, there are exactly two vertices. If two different faces intersect, we assume they either intersect at their common edge or their common vertex. Clearly the discrete notion of surfaces is very useful in computer graphics.

mesh surface

A discrete surface


A more complicated discrete surface

The main result of this post is

Theorem 1 (Discrete Gauss-Bonnet theorem) Let {K} be the Gaussian curvature and {k_g} be the geodesic curvature on a discrete surface {M}, then

\displaystyle \displaystyle \sum_{v\in \boldsymbol{V_I}} K(v)+\sum_{v\in \boldsymbol{V_B}}k_g(v)=2\pi\chi(M).

Here {\boldsymbol{V_I}} is the set of interior vertices and {\boldsymbol{V_B}} is the set of boundary vertices and {\chi(M)} is the Euler characteristic of {M}.

We will explain the notation below the fold.

Our first goal is to generalize all the notions such as boundary, geodesic curvature (or exterior angle at an vertex of a triangle), and Gaussian curvature on a smooth surface to a discrete surface.

Definition 2 We say an edge of {M} lies on the boundary if it is contained only in exactly one face. The boundary of {M} is defined as the set of all such edges.
A discrete surface with boundary

A discrete surface with boundary

Note that there can be surfaces without boundary, for example the (triangulated) sphere in {\mathbb R^3}.

A triangulated sphere

A triangulated sphere


Next we have to generalize the notion of the exterior angle of a triangle. It can be regarded as the defect, or failure for two adjacent edges (of a triangle) to form a straight angle (i.e. {{\pi}}, or {{180^\circ}}). Motivated from this, we have the following:

Definition 3 A vertex is interior if it is not a common vertex of two boundary edges, otherwise it is called a boundary vertex.
Definition 4 For an interior vertex {{v}} of a discrete surface, suppose there are exactly {{l}} faces sharing {{v}} as a common vertex, then the Gaussian curvature, or the angle defect, {{K(v)}} is defined as

\displaystyle \displaystyle K(v)= 2\pi - \sum_{i=1}^l \theta_i

where {{\theta_i}} are the (interior) angles of that {{l}} faces at the vertex {{v}}.

For example, if all the faces which shares {{v}} as a vertex all lies on a plane, then the angle defect at {{v}} is {{0}}. Intuitively, the angle defect measures how the faces meeting at {{v}} deviates from the plane. If {{K(v)>0}}, then a small circle with “radius” {{r}} (in the obvious sense) around {{v}} will have length smaller than {{2\pi r}}, thus it looks “round” near that vertex. On the other hand, if {{K(v)<0}}, then the small circle of radius {{r}} will be longer then the Euclidean circle of the same radius (i.e. {{2\pi r}}), so it looks like a saddle near here, we then say that the curvature at that point is negative.

Definition 5 For a boundary vertex {{v}} of a discrete surface, suppose there are exactly {{k}} faces sharing {{v}} as a common vertex, then the geodesic curvature {{k_g(v)}} is defined as

\displaystyle \displaystyle k_g(v)= \pi - \sum_{i=1}^k \theta_i

where {{\theta_i}} are the (interior) angles of that {{k}} faces at the vertex {{v}}.

Definition 6 For a discrete surface {{M}}, if the number of its vertices is {{V}}, that of its edges is {{E}} and that of its faces is {{F}}, then its Euler characteristic {{\chi(M)}} is defined as

\displaystyle \displaystyle \chi(M)=V-E+F.

The remarkable fact about {{\chi}(M)} is that it is a topological invariance, i.e. if we have two surfaces {M_1} and {M_2} which are homeomorphic (topologically equivalent), then their Euler characteristics are the same, and is independent of how we “triangulate” them. In other words, if we triangulate a surface in two ways, although {V}, {E} and {F} may change individually, {V-E+F} remains unchanged.

We are now ready to prove the main result.

Let {\boldsymbol{V_B}} be the set of boundary vertices and {\boldsymbol{V_I}} be the set of interior vertices. Let {V_B= |\boldsymbol{V_B}|} and {{V_I}= |\boldsymbol{V_I}|}, so {V=V_I+V_B}.

\displaystyle \displaystyle \begin{array}{rcl} &&\displaystyle \sum_{v\in \boldsymbol{V_I}} K(v) +\sum _ {v\in \boldsymbol{V_B}} k_g(v)\\ &= &\displaystyle\sum_{v\in \boldsymbol{V_I}} (2\pi - \text{sum of angles at }v)+\displaystyle\sum_{v\in \boldsymbol{V_B}} (\pi - \text{sum of angles at }v)\\ &= &2\pi V_I + \pi V_B - \displaystyle\sum_{v:\;\text{vertices}}\text{sum of angles at }v\\ &= &2\pi V_I + \pi V_B- \displaystyle\sum_{f:\;\text{faces}}\text{sum of angles of }f\\ &= &2\pi V_I + \pi V_B- \displaystyle\sum_{f:\;\text{faces}}\pi\\ &= &2\pi V_I + \pi V_B- \pi F\\ &=&\pi \left(2(V-E+F)-V_B +2E -3F\right)\\ &=&\pi \left(2\chi(M) -V_B+2E-3F\right). \end{array} \ \ \ \ \ (1)

By counting the number of directed edges, or more precisely, since each interior edge is shared by exactly two faces, and each face has exactly three edges, counting the number w.r.t. the edge orientation and w.r.t. the faces gives

\displaystyle \displaystyle 3F=2E_I + E_B

where {E_I} is the number of interior edges and {E_B} is the number of boundary edges, so that {E=E_I+E_B}.

Counting directed edges

Counting directed edges

Plugging this into the above equation, we have

\displaystyle \frac{1}{\pi}\left(\displaystyle \sum_{v\in \boldsymbol{V_I}} K(v)+\sum_{v\in \boldsymbol{V_B}}k_g(v)\right) =2 \chi(M)-V_B+E_B=2\chi(M)

as {E_B=V_B}. \Box

Remark 1 Can we combine this version of the Gauss-Bonnet theorem with the smooth version? Can we also generalize it to higher dimensions?

1. Some more remarks on {K(v)}

It is natural to ask: how does {K(v)} relate to the Gaussian curvature {K} on a smooth surface?

Indeed, {K(v)} can be regarded as the “integral” (along a small loop around {v}) of the smooth Gaussian curvature {K} “as if” the curvature is concentrated at the vertex.

To see this, let’s look at the simpler case of the discrete geodesic curvature {k_g} first. Suppose we have a piecewise smooth curve {\alpha(s)} which has a non-smooth (but continuous) point {p=\alpha(s_0)}, then we can measure the angle {\phi(s)} from a parallel vector field {E(s)} along {\alpha(s)} to the tangent vector {\alpha'(s)}. Of course there is a jump of {\phi(s)} at {s_0}, which corresponds exactly the exterior angle of {\alpha} at {s_0}. Therefore the exterior angle {\phi} at {\alpha(s_0)} corresponds to the “integral” {\Delta \phi=\int_{\Delta s} k_g ds=\int_{\Delta s}\phi'(s)ds} if we “smooth out” {\alpha} near {s_0}. In the dual sense, if we “straighten out” {\alpha} to be a geodesic outside {\left(s_0- \varepsilon, s_0+\varepsilon \right)} and “push” all the curvature near {p}, i.e. on the interval {(s_0-\varepsilon, s_0+\varepsilon)}. Then {\Delta \phi=\int_{s_0-\varepsilon}^{s_0+\varepsilon} k_g ds} tends to the exterior angle at {\alpha(s_0)} as {\varepsilon\rightarrow0}. Therefore it’s natural to define the discrete versions {k_g(v)} as the exterior angle at the boundary vertex {v}.

We now extend this notion of “exterior angle” from the boundary vertices to the interior vertices. For a piecewise smooth unit-speed curve {\alpha(s)} on a smooth surface {M}, there are two equivalent ways to define the exterior angle {\phi(s_0)} at any {s_0}.

  1. The first definition is to define {\phi(s)} as the angle measured from {\displaystyle \lim_{s\rightarrow s_0^-} \alpha'(s)} to {\displaystyle \lim_{s\rightarrow s_0^+} \alpha'(s)}.
  2. The other way is to measure the angle from {\textbf{n}_-(s_0)} to {\textbf{n}_+(s_0)}. Here {\textbf{n}_-(s_0)} is the unit normal vector of {\displaystyle \lim_{s\rightarrow s_0^-}\alpha'(s)} lying on {T_{\alpha(s_0)}M} such that {\textbf{n}_-(s_0), \displaystyle \lim_{s\rightarrow s_0^-}\alpha'(s)} forms a positively oriented basis for {T_{\alpha(s_0)}M}. The normal vector {\textbf{n}_+(s_0)} is similarly defined.

Note that in both cases, we have to fix an orientation of {M} in order for {\phi} to have a well-defined sign. Also note that the exterior angle is {0} at all smooth points, so there are only finitely many exterior angles along a simple closed piecewise smooth curve.

We generalize the notion of an exterior angle to an interior vertex using (2). Assume that our discrete surface {M} lies in {\mathbb R^3} and is orientable. Then on a small simple closed positively oriented curve {\alpha} traveling around {v}, if {\deg v=l}, there are {l} unit normal vectors (discrete Gauss map) {\textbf N_1, \cdots, \textbf{N}_l} on the {l} faces adjacent to {v} when one travels along {\alpha}. Now regard {\textbf{N}_i} as points on the unit sphere {\mathbb S^2}. The orientability condition ensures that {\textbf{N}_{i+1}\ne -\textbf{N}_i} and so {\{\textbf{N}_1, \cdots, \textbf{N}_l\}} form an {l}-sided geodesic polygon on {\mathbb S^2}.

We claim that the signed area of this geodesic polygon is {K(v)} (sign taken w.r.t. the standard orientation of {\mathbb S^2}), so that K(v) is the “exterior (solid) angle” at {v}. For simplicity let’s assume {l=\deg v=3}. Suppose {\theta_1, \cdots, \theta_3} are the interior angles at {v}. Then in this case the spherical triangle {T^*=\Delta \textbf{N}_1\textbf{N}_2 \textbf{N}_3} is the dual triangle of the spherical triangle {T} with sides {\theta_1, \theta_2, \theta_3} respectively (notice that the length of a geodesic segment on the unit sphere is exactly the polar angle it spans at the origin). Please see this post for more details. By Proposition 5 here we conclude that the interior angle of {T^*} are exactly {\pi-\theta_1}, {\pi-\theta_2} and {\pi-\theta_3}. Therefore an application of the smooth version of the Gauss-Bonnet theorem (or see this post) tells us that the area of {T^*} is

\displaystyle  \begin{array}{rl}  \textrm{Area}(T^*) =&(\pi-\theta_1+\pi-\theta_2+\pi-\theta_3 )-\pi\\ =&2\pi-\sum_{i=1}^l\theta_i\\ =&K(v). \end{array}

(If {K(v)<0} then the signed area is taken to be the negative of this geometric area of {T^*}.) Therefore we conclude that {K(v)} is the (signed) area of the geodesic polygon enclosed by {N(\alpha)} if {\alpha} is a small (positively oriented) loop around {v}.

This can be regarded as the “integral” {\int_{\Delta S}K dS} as if the curvature is “concentrated” on a small domain {\Delta S} around {v}. Recall that on a smooth surface {S}, if {p\in S} is such that {K(p)\ne 0}, then

\displaystyle K(p)= \lim_{\Omega\rightarrow p}\frac{\textrm{(Signed) Area } (N(\Omega))}{\textrm{Area}(\Omega)}.

This entry was posted in Calculus, Combinatorics, Discrete Mathematics, Geometry, Topology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s