Reading 1 – The Simplicial Complex

ddg_simplices

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:

  1. a short (2-3 sentence) summary of what you read, and
  2. 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, …).

2 thoughts on “Reading 1 – The Simplicial Complex”

  1. 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

    1. 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!

Leave a Reply