Singular complex

Simplicial complexes are useful in applications such as geometric modeling and computer graphics for computing the topology of models. Due to the complicated topological spaces, implicit, nonlinear models, and decomposition algorithms that arise in motion planning, they are insufficient for the most general problems. A singular complex is a generalization of the simplicial complex. Instead of being limited to $ {\mathbb{R}}^n$, a singular complex can be defined on any manifold, $ X$ (it can even be defined on any Hausdorff topological space). The main difference is that, for a simplicial complex, each simplex is a subset of $ {\mathbb{R}}^n$; however, for a singular complex, each singular simplex is actually a homeomorphism from a (simplicial) simplex in $ {\mathbb{R}}^n$ to a subset of $ X$.

To help understand the idea, first consider a 1D singular complex, which happens to be a topological graph (as introduced in Example 4.6). The interval $ [0,1]$ is a $ 1$-simplex, and a continuous path $ \tau :
[0,1] \rightarrow X$ is a singular $ 1$-simplex because it is a homeomorphism of $ [0,1]$ to the image of $ \tau$ in $ X$. Suppose $ {\cal G}(V,E)$ is a topological graph. The cells are subsets of $ X$ that are defined as follows. Each point $ v \in V$ is a 0-cell in $ X$. To follow the formalism, each is considered as the image of a function $ f: \{0\} \rightarrow X$, which makes it a singular 0-simplex, because $ \{0\}$ is a 0-simplex. For each path $ \tau \in E$, the corresponding $ 1$-cell is

$\displaystyle \{ x \in X \;\vert\; \tau(s) = x$    for some $\displaystyle s \in (0,1)\} .$ (6.4)

Expressed differently, it is $ \tau((0,1))$, the image of the path $ \tau$, except that the endpoints are removed because they are already covered by the 0-cells (the cells must form a partition).

These principles will now be generalized to higher dimensions. Since all balls and simplexes of the same dimension are homeomorphic, balls can be used instead of a simplex in the definition of a singular simplex. Let $ B^k
\subset {\mathbb{R}}^k$ denote a closed, $ k$-dimensional unit ball,

$\displaystyle D^k = \{ x \in {\mathbb{R}}^n \;\vert\; \Vert x\Vert \leq 1 \} ,$ (6.5)

in which $ \Vert\cdot\Vert$ is the Euclidean norm. A singular $ k$-simplex is a continuous mapping $ {\sigma}: D^k \rightarrow X$. Let $ \operatorname{int}(D^k)$ refer to the interior of $ D^k$. For $ k \geq 1$, the $ k$-cell, $ C$, corresponding to a singular $ k$-simplex, $ {\sigma}$, is the image $ C = {\sigma}(\operatorname{int}(D^k)) \subseteq X$. The 0-cells are obtained directly as the images of the 0 singular simplexes. Each singular 0-simplex maps to the 0-cell in $ X$. If $ {\sigma}$ is restricted to $ \operatorname{int}(D^k)$, then it actually defines a homeomorphism between $ D^k$ and $ C$. Note that both of these are open sets if $ k > 0$.

A simplicial complex requires that the simplexes fit together nicely. The same concept is applied here, but topological concepts are used instead because they are more general. Let $ {\cal K}$ be a set of singular simplexes of varying dimensions. Let $ S_k$ denote the union of the images of all singular $ i$-simplexes for all $ i \leq k$.

A collection of singular simplexes that map into a topological space $ X$ is called a singular complex if:

  1. For each dimension $ k$, the set $ S_k \subseteq X$ must be closed. This means that the cells must all fit together nicely.
  2. Each $ k$-cell is an open set in the topological subspace $ S_k$. Note that 0-cells are open in $ S_0$, even though they are usually closed in $ X$.

Example 6..1 (Vertical Decomposition)   The vertical decomposition of Section 6.2.2 is a nice example of a singular complex that is not a simplicial complex because it contains trapezoids. The interior of each trapezoid and triangle forms a $ 2$-cell, which is an open set. For every pair of adjacent $ 2$-cells, there is a $ 1$-cell on their common boundary. There are no 0-cells because the vertices lie in $ {\cal C}_{obs}$, not in $ {\cal C}_{free}$. The subspace $ S_2$ is formed by taking the union of all $ 2$-cells and $ 1$-cells to yield $ S_2 = {\cal C}_{free}$. This satisfies the closure requirement because the complex is built in $ {\cal C}_{free}$ only; hence, the topological space is $ {\cal C}_{free}$. The set $ S_2 = {\cal C}_{free}$ is both open and closed. The set $ S_1$ is the union of all $ 1$-cells. This is also closed because the $ 1$-cell endpoints all lie in $ {\cal C}_{obs}$. Each $ 1$-cell is also an open set.

One way to avoid some of these strange conclusions from the topology restricted to $ {\cal C}_{free}$ is to build the vertical decomposition in $ \operatorname{cl}({\cal C}_{free})$, the closure of $ {\cal C}_{free}$. This can be obtained by starting with the previously defined vertical decomposition and adding a new $ 1$-cell for every edge of $ {\cal C}_{obs}$ and a 0-cell for every vertex of $ {\cal C}_{obs}$. Now $ S_3 = \operatorname{cl}({\cal C}_{free})$, which is closed in $ {\mathbb{R}}^2$. Likewise, $ S_2$, $ S_1$, and $ S_0$, are closed in the usual way. Each of the individual $ k$-dimensional cells, however, is open in the topological space $ S_k$. The only strange case is that the 0-cells are considered open, but this is true in the discrete topological space $ S_0$. $ \blacksquare$

Steven M LaValle 2012-04-20