5.3 Data Structure Storage Mechanism

As given in Section 1.6, the chain concept can be used in conjunction with the fiber bundle concept, by the so-called intrinsic incidence information of each $p$ -skeleton. In this work, the information regarding the cell topology is stored within the poset, where the complex topology information, for the local case, has to be stored explicitly. To enable an efficient means for this type of storage, an additional concept of a connection matrix [53] is introduced not only to derive neighborhood information of cells, but also to enable different types of traversal mechanisms. To enable vertex-on-cell traversal, only the minimal information has to be stored. To enable a full traversal hierarchy, not only the vertex-on-cell but also the cell-on-vertex information has to be stored. Based on this twofold incidence information, the full hierarchy of traversal is available. It is also of utmost importance to store the local orientation of each cell to avoid additional implementation overhead for the subsequent applications.

The basic property for a consistent data structure is the total ordering of the $m_n$ $n$ -cells of an $n$ -dimensional complex ${\ensuremath{\mathfrak{K}}}$ , whereas the vertices of a cell are modeled by a partial ordering, as introduced in Section 1.3.1. Based on the lattice property of a cell complex, which every complex in this work fulfills, each cell can be uniquely identified by its set of vertices, e.g., a $p$ -cell:

$$\ensuremath{\tau_{p}^{}} = \{ v_{k_0}, .., v_{k_p} \}$$ (5.2)

For the minimal case, the only information to be stored is the connectivity information of the cell-vertex relation with the corresponding orientation. The following connection matrix with a size of $m_n \times m_0$ is obtained. With additional data storage concepts, this information can be stored as a sparse $m_n \times k$ matrix, with a constant $k = \textnormal{number of vertices of a cell}$ for homogeneous cell complexes. The connection matrix, where $j$ stands for the $p$ -cells and $i$ for the 0 -cells is then given by:

$$C_{j}^{i} = \begin{cases}+1 \quad \; \textnormal{if vertex}  \en... ... \ensuremath{\tau_{n}^{j}} \;0 \quad \;\; \textnormal{otherwise} \end{cases}$$ (5.3)

An example for a connection matrix is depicted in Figure 5.9, where the zeros are omitted, thus revealing the sparse structure of the matrix.

Figure 5.9: Connection matrix $C_j^i$ for a cell complex.

The connection matrix, obtained by a mesh generator, thereby enables the following traversal operations:

• Vertex-on-cell: using a horizontal query
• Cell-on-vertex: using a vertical query

By using the poset mechanism and the stored orientation information to initialize the poset structure accordingly, the following additional traversal mechanism are available:

• Oriented vertex-on- cell
• Oriented edge-on- cell
• Oriented facet-on-cell

Using additional evaluation mechanisms of the connection matrix, adjacence traversal is also possible:

• Vertex-to-vertex
• Edge-to-edge
• Facet-to-facet
• Cell-to-cell

By evaluating the adjacence information, boundary operators can also be derived.