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.

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 beveryeasy to construct a counter-example!)Note:for Exercise 1.3, you donotneed to construct explicit examples of surfaces that achieve a minimal number of irregular vertices.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.

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?

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.

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

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…

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