Back to the PSciCo homepage

Keywords

Vertex , simplex , face , oriented simplex , simplicial complex , simplicial set

Simplicial Complexes

Simplicial complex library contains the definition and implementation of simplicial complexes and simplicial sets for arbitrary dimensions. The library allows the programmer to build a simplicial complex or a set, associate data with the contained simplices, operate on the contained simplices and data, and query the complex or the set with powerful library functions.

In some dimension d, a vertex is a point in the d-dimensional space. A simplex is the convex hull of d+1 vertices. For example, a triangle is a simplex in 2 dimensions (or a 2-dimensional simplex). A simplex can be represented as an unordered set of vertices, for example, {a, b, c} represents a triangle with corners a, b, and c. In many applications, however, it is important to tell whether a vertex lies inside or outside of a simplex (or equivalently, whether a vertex is visible or not from the simplex). To do this, we use an oriented simplex . In two dimension, an oriented simplex, a triangle, has two orientations, an inside and an outside determined by the ordering of its vertices. Hence, we use an ordered set to represent oriented simplices, for examples, (a, b, c) represents the inside, and (c, b, a) represents the outside of the triangle {a, b, c}. A face of a simplex is a one lower dimensional simplex belonging to the simplex. For example, the line (a,b) is a face of the simplex (a, b, c).

Oriented simplices are building blocks of simplicial complexes and sets. I will refer to an oriented simplex simply as a simplex from now on. The library provide facilities to enable the programmer to create a simplex from an ordered set of vertices corresposponsing to its corners and manipulate the simplex. Based on simplices, we define a simplicial complex as a set of fixed-dimensional simplices satisfying the following condition. The intersection of two d-dimensional simplices is a face of the intersecting simplices. A simplicial set is similar to a simplicial complex but more general. A simplicial set allows three or more simplices share the same face.

A simplicial complex operates on oriented simplices. The programmer can create a simplicial complex by calling the new function and passing the dimension of the simplicial complex as a parameter. The programmer can then create and add simplices to the simplicial complex. The interface allows the programmer to remove a simplex from the simplicial complex, search for arbitrary dimensional simplices, or find simplices that has a given simplex as a face in the simplicial complex. Also the programmer can associate data with each simplex; the library provides additional functions to extract or manipulate the data associated with a simplex.

Much like a simplicial complex, a simplicial set can be built by creating an empty set and subsequently adding and removing simplices from the set. Unlike a simplicial complex, however, a simplicial set operates on unoriented simplices. Simplicial sets provide the programmer with functions similar to the simplicial complexes to manipulate the data and the simplices in the set, as well as query the set.


Back to the PSciCo homepage.