next up previous contents
Next: What is Voronoi diagram Up: Voronoi Diagram and Delaunay Previous: Voronoi Diagram and Delaunay   Contents

What is cell complex? What is triangulation?

A cell complex or simply complex in $ R^d$ is a set $ K$ of convex polyhedra (called cells) in $ R^d$ satisfying two conditions: (1) Every face of a cell is a cell (i.e. in $ K$), and (2) If $ P$ and $ P'$ are cells, then their intersection is a common face of both. A simplicial complex is a cell complex whose cells are all simplices.

The body $ \vert K\vert$ of a complex $ K$ is the union of all cells. When a subset $ P$ of $ R^d$ is the body of a simplicial complex $ K$, then $ K$ is said to be a triangulation of $ P$. For a finite set $ S$ of points in $ R^d$, a triangulation of $ S$ is a simplicial complex $ K$ with $ \vert K\vert=conv(S)$.

Komei Fukuda 2004-08-26