For your first reading assignment, your goal will be understand of the idea of a *simplicial complex*—or one of its many generalizations, if you’re already familiar with this idea (see below). Simplicial complexes are the basis of many of the algorithms we’ll study in this class—and for a vast array of algorithms used in mesh processing, scientific computing, and Hollywood. They are also one common way to discretize *topological spaces*, which are the starting point for our study of geometry in the smooth setting.

We will discuss this concept further in class, so don’t worry if you’re utterly confused! Also, *please feel free to discuss and ask questions here*, by posting in the comments.

Listed below are some suggested readings (from *“beginner”* to *“expert”*). For this first reading assignment, you are also free to search for references that you find easier or more interesting:

*Simplicial Complex (up through & including “Closure, Star, and Link”)*– Perhaps it seems lazy to send a link to the Wikipedia (which is the first result on Google), but then again, I wrote much of this page many years ago—and made the figures. It would be a useful exercise to contrast with*Abstract Simplicial Complex*.*Simplicial Complexes*and*Simplicial Complexes*– two brief introductions, both by Herbert Edelsbrunner.*Cell Complexes*– more advanced (and nicely illustrated) introduction by Jeff Erickson.*Algebraic Topology (pp. 102–104)*– very nice (and free!) book by Allen Hatcher, who here discusses $\Delta$-complexes, a close cousin of simplicial complexes. Those of you who want to go really deep might also take a look at pp. 5–10 on cell (CW) complexes, as well as an additional supplement on*simplicial CW structures*.

Finally:

*A Survey of Efficient Structures for Digital Geometry Processing, Section 2.2*– I include this reference not because it is particularly good introduction to simplicial complexes—in fact, there are some errors!—but because it gives a rough sense of the kind of document you will write for your final project (albeit a bit different in focus).

**Submission:** Please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than **10:00 AM on Tuesday, January** 19; please include the string **DDGSpring2016 **in your subject line, so that we can be sure we catch your submission**.** Your email for readings should always include:

- a short (2-3 sentence) summary of what you read, and
- at least one question about something you found confusing / incomplete / not addressed.

For this particular reading, your summary should include a *clear, concise* definition for a simplicial complex, i.e., one that could be used to quickly communicate the idea to one of your peers *without ambiguity*. For those of you already familiar with simplicial complexes, try to summarize the taxonomy of different complex types (simplicial complex, oriented simplicial complex, $\Delta$-complex, CW-complex, simplicial set, …).

Hello!

I am a complete beginner to this idea (do bear with me!) and having gone through the first couple of readings, as well as some additional material elsewhere, I have some questions which I have consolidated here.

1. In line 2 of the wiki page on simplices (https://en.wikipedia.org/wiki/Simplex), should that be $\mathbb{R}^{k}$ instead of $\mathbb{R}^{k+1}$ ? Since it’s a k-dimensional polytope?

2. A related question – on the other hand, the k-dimensional standard simplex is formed from points in $\mathbb{R}^{k+1}$ right? And it is the additional constraint of the basis vectors that makes it k-dimensional instead of (k+1)-dimensional?

3. I read that the boundary of a boundary of a simplex is 0. I can see this working for a simple example, but I was unable to find a general proof of this. Would anyone happen to have any references?

4. For the theorem that every k-dimensional abstract complex has a geometric realization in $\mathbb{R}^{2k+1}$, I understand the proof – but my intuition seems to tell me $\mathbb{R}^{k}$. For, if I can accommodate the simplex (set) of highest dimension (k) of the complex (family of sets), which I can do in $\mathbb{R}^{k}$ can I not accommodate the other simplices (of dimension $\leq k$) in that space as well, by appropriately gluing them together? I am trying to figure out where my intuition is wrong.

Thanks for any help,

Shushman

Here are just some of my thoughts that might help you get a better understanding of this material.

1. It is okay for these $k+1$ points to lie in $\mathbb R^{k+1}$, these points can lie in any $\mathbb R^m$ where $m\geq k$. Using barycentric coordinates, we have that it is natural for a $k$-simplex to be constructed from points in $\mathbb R^{k+1}$. The convex hull of these $k+1$ points gives us a face that is isomorphic to some subset of $\mathbb R^k$. This set that we are taking the convex hull of doesn’t contain the origin, otherwise we would get a $(k+1)$-dimensional polytope. A $k$-dimensional polytope can lie in any higher dimension.

2. Using the convex hull of these basis vectors we have that $\Delta^k$ is formed from vectors in $\mathbb R^{k+1}$.

3. We have that $\partial_{n+1}\circ\partial_{n}=0$ when we work with chains (note: chains are (free abelian) groups, so every element has an inverse) of an oriented $\Delta$-complex. It doesn’t necessarily make sense to me that the boundary of the boundary of a nonoriented simplex would be 0, since we can’t necessarily cancel anything out. Hatcher’s Algebraic Topology provides a good reference of this at the beginning of the chapter on Simplicial Homology.

4. Let’s look at an example that might help you see why $\mathbb R^k$ is not sufficient for the geometric representation of any $k$-dimensional abstract simplicial complex. Consider any 1-dimensional abstract simplicial complex (a graph with straight edges). The geometric realization theorem tells us that we need at least $\mathbb R^3$ to geometrically realize all of these 1-dimensional abstract simplicial complexes. Try seeing that if we only consider $\mathbb R^1$ it would be very difficult to represent all graphs. Similarly, we know that there exist nonplanar graphs so we need at least $\mathbb R^3$.

Let me know if there’s anything that doesn’t add up / any further questions or clarifications you have!