To model space and time within the regime of a finite computer representation, the continuous domain has to be projected onto finite domains or cells. This chapter describes how these cells can be introduced and manipulated algebraically1.1, and is mainly based on the work of Jänich [2] for common topological terms, Berti [18] for the cell complexes, and Zomorodian [19] for the computational topology part. The most basic property of topology is that it separates global space properties from local geometric attributes. Additionally, and more importantly for this work, it provides a precise notation and language for discussing and handling various properties.
Topological spaces offer several operations for sets and subsets. The formal definition of a topological space is given next, where only the concept of a set is implied:
The second property (T2) states that arbitrary intersections of
subsets have to be in the topological space again. Also the union (T3)
of subsets has to be contained in the space. These properties are
later used to describe inter-dimensional elements for the complex,
such as edges of a cell. An example is given in the following which
presents a basic set
and the corresponding
topology. This pair of the original set and the set of subsets
generates the topological space. Vertices are modeled by the
singletons
,
, and
.
(1.23) |
To introduce the concept of a topological base, it is necessary to create a topology on a set in which a set of subsets of are open sets.
With these definitions, sets of subsets can be handled with additional properties in a common way. The common definition for a topological space is very general and allows several topological spaces which are not useful in the field of data structures, e.g., a topological space with a trivial topology . Therefore the basic mechanism of separation within a topological space is introduced. Of a hierarchy of possible separation conditions augmenting the topological space axioms, an important characteristic is the Hausdorff condition.
Common data structures in the field of scientific computing embody the separation characteristics of a Hausdorff space. The assumption to be made is that all scientific data can be modeled by the concept of a Hausdorff space. This can be seen as a generalization of Butler's model, which is based on the assumption that all scientific data can be modeled by trivial fiber bundles [21].
The concept of a cover is introduced to equip a topological space with a type of dimension.
If a topological space is homeomorphic to with , then its dimension is . If a space does not have a Lebesgue covering dimension for any , it is called infinite-dimensional. The dimension of the empty set is defined as . It is important to note that the reverse it not always true, which means that a topological space with dimension is not necessarily homeomorphic to .
Another fundamental topological concept is compactness, which may be regarded as a substitute for finiteness. It frequently compensates for the restriction to finite intersections in axiom (T2) by allowing arbitrary sets of open sets to be reduced to finite sets of sets.
An important part of the characterization of data structures is the possibility to identify the object with the highest dimension, modeled by the concept of an open cell.
Collections of cells form larger structures, so-called complexes which are identified by the cell with the highest dimension, e.g., a -dimensional space contains -cells.
With the concepts already introduced, the concept of a cell complex can be formulated.
Definition: CW-Complex
[2]
A pair
, with
a Hausdorff space and a
decomposition
into cells is called a CW-Complex if and only
if the following axioms are satisfied:
A CW-cell complex with the underlying space guarantees that all inter-dimensional objects are connected in an appropriate manner, such that is obtained from by attaching -cells to each -cell and . The respective subspaces are called the -skeletons of the cell complex.
A -cell describes the cell with the highest dimension, e.g., -cell edges and -cell triangles. For this work the most important property of a CW-complex can be explained by using different -cells and consistently attaching sub-dimensional cells to the -cells. This fact is taken care of by the mapping function. For the common case a -cell can be described by the oriented collection of the 0 -cells, e.g., for a simplex cell , which is introduced in more detail in Section 1.3.1.
So far all mechanisms to handle the underlying topological space of data structures have been introduced. Each subspace can be uniquely characterized by its dimension. All subspaces are connected appropriately by the concept of a finite CW-cell complex.
The following section introduces concepts of order theory to formalize the combinatorial structure of cells and the global structure of cell complexes [54]. First, the most basic notion of a binary relation is introduced which is a specialization of the relation concept, where two arguments are used.
Figure 1.2: Left: Integers form a chain, totally ordered by . Middle: Incomparable items forming an anti-chain. Right: The power-set of ordered by as a partially ordered set. |
Finally, the concept of covering is needed. For ordered by , it is said is covered by (written ), if and for any , implies . This means that there is no element of "between" and . Equivalently it can be said that covers .
It can be seen that in interpreting diagrams, it does not matter whether one node is above or below another unless there is a monotonic path between them; and that if there is a monotonic path from through one or more nodes down to , there is no separate edge directly from to , as can be seen in Figure 1.2.
The of two elements corresponds to their geometric intersection , the to the element of least dimension containing both of them . The of two elements may be the whole mesh. The poset of a convex polytope is an atomic and coatomic lattice. For an arbitrary complex, the poset is in general not a lattice. If a grid's lattice is atomic, it means that -cells are uniquely determined by their vertex sets if the lattice is coatomic, the vertex sets of -cells for can be determined from the knowledge of the vertex sets of the -cells alone.
Order concepts for sets just introduced can be used to formalize the internal structure of an arbitrary -cell, e.g., with the Hasse diagram. A simplex cell is thereby distinguishable from a cuboid cell type in several dimensions as depicted in Figure 1.3 and Figure 1.4, respectively.
Also, sub-cells such as the corresponding edges and facets and their direct relations to the cell can be identified. An example of extracting all edges of the simplex cell which corresponds with the middle layer of the Hasse diagram can also be seen in Figure 1.3. Another important fact to mention is that the topological structure and the corresponding order hierarchy is invariant of the type of cell used. The -layer of the cuboid cell represents the edges of this type of cell.
As a higher dimensional example, a three-dimensional simplex example is given in Figure 1.5.
Here, the -cells are the facets, and, in this particular example, triangles. By using the actual dimension of the -cell and deriving the cells only by means of the order structure, a flexible framework can be built, where an important property for characterizing cell complexes is required, the regularity of cells and the complex. If the mapping function extends to a homeomorphism on the whole of , then the -cell is regular; its sides are then homeomorphic to a decomposition of , the boundary. The cell complex is regular if all cells are regular. The lattice property of a cell complex then guarantees that intersections of the vertex sets of elements always uniquely define a lower dimensional element.
In contrast to the internal cell topology, a cell complex requires adjacence information of cells. There are different possibilities of storing this information efficiently [35,53]. This work develops an abstract means of storing all different types of cells orthogonally, based on the cell topology of the complex topology. For dimensions greater than one, Figure 1.6 illustrates the complex topology of a 2-simplex cell complex where the bottom sets are now the cells. The rectangle in the figure marks the relevant cell number.
The topology of the cell complex is only available locally because of the fact that the top set can have an arbitrary number of elements. The term meta-cell is used to describe various subsets with a common name. In other words, there can be an arbitrary number of triangles in this cell complex attached to the innermost vertex.
Figure 1.7 presents the complex topology of a cuboid cell complex. The rectangle in the figure marks the main cell (5) under consideration. As can be seen, the number of attached cells is constant inside the space. The topology of the cell complex can thereby be used as a globally known property.