Simplicial Complex

For this definition, it is assumed that $ X = {\mathbb{R}}^n$. Let $ p_1$, $ p_2$, $ \ldots $, $ p_{k+1}$, be $ k+1$ linearly independent6.5 points in $ {\mathbb{R}}^n$. A $ k$-simplex, $ [p_1,\ldots,p_{k+1}]$, is formed from these points as

$\displaystyle [p_1,\ldots,p_{k+1}] = \left\{ \sum_{i=1}^{k+1} \alpha_i p_i \in ...
...\geq 0 \mbox{ for all } i \mbox{ and } \sum_{i=1}^{k+1} \alpha_i = 1 \right\} ,$ (6.3)

in which $ \alpha_i p_i$ is the scalar multiplication of $ \alpha_i$ by each of the point coordinates. Another way to view (6.3) is as the convex hull of the $ k+1$ points (i.e., all ways to linearly interpolate between them). If $ k=2$, a triangular region is obtained. For $ k=3$, a tetrahedron is produced.

For any $ k$-simplex and any $ i$ such that $ 1 \leq i \leq k+1$, let $ \alpha_i=0$. This yields a $ (k-1)$-dimensional simplex that is called a face of the original simplex. A 2-simplex has three faces, each of which is a 1-simplex that may be called an edge. Each 1-simplex (or edge) has two faces, which are 0-simplexes called vertices.

To form a complex, the simplexes must fit together in a nice way. This yields a high-dimensional notion of a triangulation, which in $ {\mathbb{R}}^2$ is a tiling composed of triangular regions. A simplicial complex, $ {\cal K}$, is a finite set of simplexes that satisfies the following:

  1. Any face of a simplex in $ {\cal K}$ is also in $ {\cal K}$.
  2. The intersection of any two simplexes in $ {\cal K}$ is either a common face of both of them or the intersection is empty.
Figure 6.15 illustrates these requirements. For $ k > 0$, a $ k$-cell of $ {\cal K}$ is defined to be interior, $ \operatorname{int}([p_1,\ldots,p_{k+1}])$, of any $ k$-simplex. For $ k = 0$, every 0-simplex is a 0-cell. The union of all of the cells forms a partition of the point set covered by $ {\cal K}$. This therefore provides a cell decomposition in a sense that is consistent with Section 6.2.2.

Figure 6.15: To become a simplicial complex, the simplex faces must fit together nicely.
\begin{figure}\begin{center}
\begin{tabular}{cc}
\psfig{file=figs/badscomp.eps,w...
...licial complex & A simplicial complex \\
\end{tabular}\end{center}
\end{figure}

Steven M LaValle 2020-08-14