Next: 1.4 Computational Topology Up: 1. Mathematical Concepts Previous: 1.2 Physical Fields and

Subsections

# 1.3 Topological Toolkit

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:

Definition 3 (Topology)   A topological space consists of a set and a set of subsets, called open sets, of such that:
• (T1) and .
• (T2) a finite intersection of members of is in .
• (T3) an arbitrary union of members of is in .

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 .

To handle all subsets in a concise way, the concept of a subspace is introduced.

Definition 4 (Subspaces)   Let be a topological space. Any subset of inherits a topology in a natural way. It is given by:

 (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.

Definition 5 (Bases)   If is already closed under finite intersections, then can be defined to be those sets which are unions of sets in . Then satisfies (T1), (T2), and (T3) and is said to be a basis for .

In general, to obtain a topology containing one has to first form , the set of sets which are finite intersections of members of , and then define to be all arbitrary unions of members of . In this case is called a sub-basis for .

Definition 6 (Homeomorphism)   A homeomorphism is a onto function, such that both are continuous.

Then, is homeomorphic to , . This means that and have the same topological type. Homeomorphisms are topological isomorphisms.

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.

Definition 7 (Hausdorff spaces)   The topological space is said to be Hausdorff if, given with , there exist open sets such that and .

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.

Definition 8 (Cover)   A cover of a set is a set of nonempty subsets of whose union is .

A cover is an open cover if it is contained in the topology.

Definition 9 (Covering Dimension)   A topological space has a (Lebesgue) covering dimension if any open cover has a second open cover , the refinement, where each element is a subset of an element in the first cover such that no point is included in more than elements.

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.

Definition 10 (Compactness)   Let be a topological space and let . The set is called an open cover of if . A finite subset of whose union still contains is a finite sub-cover. It can then be said that is compact if every open cover of has a finite sub-cover.

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.

Definition 11 (Open Cell)   A subset of a Hausdorff space is an open cell if it is homeomorphic to the interior of an open -dimensional ball .

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.

Definition 12 (Decomposition)   A decomposition of a topological space is a decomposition of into subspaces.

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:

• (C1) mapping function: for each -cell a continuous function exists, which transforms homeomorphically onto the cell and in the union of maximal dimensional cells. represents an -dimensional closed unit ball and represents the sides of .
• (C2) finite hull: the closed of each cell connects only with a finite number of other cells.
• (C3) weak topology: is open if and only if each is open.

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.

## 1.3.1 Order Theory and Sets

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.

Definition 13 (Binary relation)   A binary relation is a subset of the Cartesian product of two sets and . That is, any is a binary relation.

Based on this concept a partial order is defined. A partial order is required to create a hierarchy for our subsets, which can then be used to create our traversal mechanisms.

Definition 14 (Partial order)   A partial order is a binary relation that satisfies the following three properties:
• (PO1) Reflexivity: .
• (PO2) Antisymmetry: if and , then .
• (PO3) Transitivity: if and , then .

Definition 15 (Partial order on a topological space)   Let be a Hausdorff space. For any , a binary relation on : , if and only if is defined, where represents the closure for a set within a topological space, where a closure is the intersection of all closed sets containing . Then this binary relation is a partial order.

Definition 16 (Ordered Sets)   Let be a set and be a (partial) order on . Then and form a (partially) ordered set.

To give examples for ordered sets, Figure 1.2 illustrates the possible terms:
• If the order is total, so that no two elements of are incomparable, then the ordered set is a totally ordered set, called chain. A formal definition is then given in Section 1.4.

• If no two elements are comparable unless they are equal, then the ordered set is an anti-chain.

• If has two or more incomparable elements, then the ordered set is a partially ordered set or poset. One example of an incomparable expression is with .

 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.

Definition 17 (Extrema of Partial Ordered Sets [54])   Let be an ordered set.
• is said to be maximal in if and only if there is no such that . A set may have any number of maximal elements, including none.
• If is 's only maximal element, then is the maximum of .
• The maximum element (if it exists) is also called the top of and is denoted by .
• Dually, is said to be minimal in if and only if there is no such that . A set may have any number of minimal elements, including none.
• If is 's only minimal element, then is the minimum of .
• The minimum element (if it exists) is also called the bottom of and is denoted by .

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 .

Definition 18 (Hasse Diagram)   A Hasse diagram of an ordered set is a graph in which:
• Each node corresponds to an element of the set,
• Each edge corresponds to a covering relation between the nodes it connects, and
• If is covered by ( ), then the node for is drawn in a lower position than the node for .

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.

Definition 19 (Lattice [18])   A lattice is a bounded poset in which any two elements posses a unique maximal lower bound and a unique minimal upper bound .

A lattice, e.g., for -simplices, is atomic, if each element is the of elements of dimension (the atoms), it is coatomic, if each element is the of elements of maximal dimension (the coatoms).

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.

## 1.3.2 Cell Topology

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.

 Figure 1.3: Cell topology of a simplex cell in two dimensions.

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.

 Figure 1.4: Cell topology of a cuboid cell in two dimensions.

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.

## 1.3.3 Complex Topology

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.

#### Footnotes

... algebraically1.1
Appendix A reviews necessary common terms.

Next: 1.4 Computational Topology Up: 1. Mathematical Concepts Previous: 1.2 Physical Fields and

R. Heinzl: Concepts for Scientific Computing