Homework 1: Topological Invariants of Discrete Surfaces

Homework is due by 4:30 pm next Wednesday, October 17th and can be handed in outside 329 Annenberg, or electronically by emailing keenan@cs.caltech.edu. Homework will be graded not only on the basis of correctness, but also on presentation! Remember that proofs are meant for human beings, not for machines. Legible handwriting, complete sentences, an outline of your approach, and illustrations (where appropriate) are all strongly recommended if you wish to receive a good score.

 

Euler Characteristic

 

Exercise 1.1: Polyhedral Formula A topological disk is, roughly speaking, any shape you can get by deforming the region bounded by a circle without tearing it, puncturing it, or gluing its edges together. Some examples of shapes that are disks include a flag, a leaf, and a glove. Some examples of shapes that are not disks include a circle (why?), a ball, a sphere, a DVD, a donut, and a teapot. A polygonal disk is any disk constructed out of simple polygons. Similarly, a topological sphere is any shape resembling the standard sphere, and a polyhedron is a sphere made of polygons. More generally, a piecewise linear surface is any surface made by gluing together polygons along their edges; a simplicial surface is a special case of a piecewise linear surface where all the faces are triangles. The boundary of a piecewise linear surface is the set of edges that are contained in only a single face (all other edges are shared by exactly two faces). For example, a disk has a boundary whereas a polyhedron does not. You may assume that surfaces have no boundary unless otherwise stated.

Show that for any polygonal disk with $V$ vertices, $E$ edges, and $F$ faces, the following relationship holds:

\[ V - E + F = 1 \]

and conclude that for any polyhedron $V – E + F = 2$.

Hint: use induction. Note that induction is generally easier if you start with a given object and decompose it into smaller pieces rather than trying to make it larger, because there are fewer cases to think about.

 

Euler-Poincaré Formula

Clearly not all surfaces look like disks or spheres. Some surfaces have additional handles that distinguish them topologically; the number of handles $g$ is known as the genus of the surface (see illustration above for examples). In fact, among all surfaces that have no boundary and are connected (meaning a single piece), compact (meaning closed and contained in a ball of finite size), and orientable (having two distinct sides), the genus is the only thing that distinguishes two surfaces. A more general formula applies to such surfaces, namely

\[ V - E + F = 2 - 2g, \]

which is known as the Euler-Poincaré formula. (You do not have to prove anything about this statement, but it will be useful in later calculations.)

 

Tessellation

 

Exercise 1.2: Regular Valence

The valence of a vertex in a piecewise linear surface is the number of faces that contain that vertex. A vertex of a simplicial surface is said to be regular when its valence equals six. Show that the only (connected, orientable) simplicial surface for which every vertex has regular valence is a torus ($g=1$). You may assume that the surface has finitely many faces.

Hint: apply the Euler-Poincaré formula.

 

Exercise 1.3: Minimally Irregular Valence Show that the minimum possible number of irregular valence vertices in a (connected, orientable) simplicial surface $K$ of genus $g$ is given by

\[
m(K) = \begin{cases}
4, & g = 0 \\
0, & g = 1 \\
1, & g \geq 2,
\end{cases}
\]

assuming that all vertices have valence at least three and that there are finitely many faces.

 

Exercise 1.4: Mean Valence Show that the mean valence approaches six as the number of vertices in a (connected, orientable) simplicial surface goes to infinity, and that the ratio of vertices to edges to faces hence approaches

\[ V:E:F = 1:3:2. \]

 

Discrete Gaussian Curvature

 

Exercise 1.5: Area of a Spherical Triangle Show that the area of a spherical triangle on the unit sphere with interior angles $\alpha_1$, $\alpha_2$, $\alpha_3$ is

\[ A = \alpha_1 + \alpha_2 + \alpha_3 - \pi. \]

Hint: consider the areas $A_1$, $A_2$, $A_3$ of the three shaded regions (called “diangles”) pictured below.

 

Exercise 1.6: Area of a Spherical Polygon Show that the area of a spherical polygon with consecutive interior angles $\beta_1, \ldots, \beta_n$ is

\[ A = (2-n) \pi + \sum_{i=1}^n \beta_i. \]

Hint: use the expression for the area of a spherical triangle you just derived!

 

Exercise 1.7: Angle Defect Recall that for a discrete planar curve we can define the curvature at a vertex as the distance on the unit circle between the two adjacent normals. For a discrete surface we can define (Gaussian) curvature at a vertex $v$ as the area on the unit sphere bounded by a spherical polygon whose vertices are the unit normals of the faces around $v$. Show that this area is equal to the angle defect

\[ d(v) = 2\pi - \sum_{ f \in F_v } \angle_f(v) \]

where $F_v$ is the set of faces containing $v$ and $\angle_f(v)$ is the interior angle of the face $f$ at vertex $v$.

Hint: consider planes that contain two consecutive normals and their intersection with the unit sphere.

 

Exercise 1.8: Discrete Gauss-Bonnet Theorem Consider a (connected, orientable) simplicial surface $K$ with finitely many vertices $V$, edges $E$ and faces $F$. Show that a discrete analog of the Gauss-Bonnet theorem holds for simplicial surfaces, namely

\[ \sum_{ v \in V } d(v) = 2 \pi \chi \]

where $\chi = |V| – |E| + |F|$ is the Euler characteristic of the surface.

7 Responses to “Homework 1: Topological Invariants of Discrete Surfaces”

  1. Keenan Crane says:

    Update: Exercise 1.4 has been fixed to say “(connected, orientable) simplicial surface” instead of “triangle mesh.” I’ll give one bonus point to the first person who posts a comment clearly explaining what the difference is and gives a counterexample for triangle meshes. (Hint: should be very easy to construct a counter-example!)

  2. Keenan Crane says:

    Note: for Exercise 1.3, you do not need to construct explicit examples of surfaces that achieve a minimal number of irregular vertices.

  3. nicwoodward says:

    We can consider the simple case of an infinite row of triangles in the \/\/\/\/\/\/ fashion where E:F->2 because E=2F+1 always for this.

    A more interesting example would be starting with a single triangle and then drawing a triangle in each edge, and warping that to become a regular polygon of size 6. Then repeat the process infinitely many times. The triangle mesh should approach the Poincare Hyperbolic disk.

    I cannot find the explicit difference defined here, though I believe it is the difference between an open and a closed surface. Triangle meshes are not necessarily closed and therefore you can have many edges which do not join two polygons, but for the closed case there will always be two polygons touching each edge.

    • Keenan Crane says:

      Hmm… \(E=2F+1\)? I think you can count better than that. ;-)

      Yeah, I didn’t really say what a “triangle mesh” was, did I? That’s because it’s a colloquial term and can mean a lot of different things to a lot of different people. But if someone tells you they’re working with a “triangle mesh,” it’s usually (but only usually!) safe to assume that they at least have the structure of a simplicial complex.

      I’m not sure what you mean about the PoincarĂ© disk. Sure, if you start out with an equilateral triangle then the limit of your process is a circular disk. But where does a hyperbolic metric show up?

      • nicwoodward says:

        Here is a quite descriptive .gif of the Poincare hyperbolic disk.
        http://mathworld.wolfram.com/images/gifs/poincare.gif

        Also I am quite sure about E=2F+1, since for F=1 E=3 and then each face you add is an extra 2 edges.

        However, I will need to think about these definitions more closely to understand why this change was needed, because if our triangle mesh is required to be closed and the size of triangles does not go to 0 in the vertex limit, I cannot see a problem with the original statement.

        • Keenan Crane says:

          Ah, ok — yes, you’re right. I just misinterpreted your ASCII art. Bonus point! :-D

          The original statement didn’t include the qualifications “closed, connected.” So for one thing, you could have a disjoint union of \(n\) tetrahedra (whose statistics don’t change as \(n\) goes to \(\infty\)). But the thing I really wanted you to think about is that a general simplicial complex (or “triangle mesh”) doesn’t even have to be manifold. So for instance, you could glue together a bunch of triangles along a single shared edge, kind of like a rolodex* — then you’d have the same number of vertices as faces (plus two), and twice as many edges as faces (plus one).

          *This is a really bad analogy in 2012…

  4. nicwoodward says:

    The second example is also a counterexample because E=2F+1 for each iteration.