Abstract cell complex

In mathematics, an abstract cell complex (also abstract cell complex ) is an abstract set of "cells" with a binary relation ("contained in the end of") and a mapping into the non-negative whole numbers ("dimension"). The complex is called “abstract” because the “cells” are not subsets of a Euclidean space , as is the case with simplicial complexes or CW complexes . Abstract cell complexes play an important role in image analysis and in computer graphics .

motivation

In topology one often uses (geometric) cell complexes, which are composed of (open or closed) cells, i. H. Subspaces homeomorphic to (open or closed) spheres in Euclidean space. It is usually assumed that it is a CW complex . ( Simplizial complexes are an even more special term .) For applications in image processing, among other things, it is useful to use abstractly defined cell complexes instead of geometric cell complexes.

definition

An abstract cell complex is given by ${\displaystyle K=(S,\rho ,dim)}$

• a quantity , ${\displaystyle S}$
• a binary relation on , ${\displaystyle \rho }$ ${\displaystyle S}$
• a function , ${\displaystyle dim:S\rightarrow \mathbb {N} \cup \left\{0\right\}}$

which satisfy the following axioms:

• from and follows , ${\displaystyle x\rho y}$ ${\displaystyle y\rho z}$ ${\displaystyle x\rho z}$
• from follows . ${\displaystyle x\rho y}$ ${\displaystyle dim(x)<dim(y)}$

As a rule, according to Tucker, the following additional axiom is assumed:

• If and , then there is a with and . ${\displaystyle x\rho z}$ ${\displaystyle dim(z)-dim(x)>1}$ ${\displaystyle y\in S}$ ${\displaystyle x\rho y}$ ${\displaystyle y\rho z}$

Various authors use additional axioms.

Elements of are called cells. In the special case of a geometric cell complex, the dimension is the cell and means that the cell is located at the end of the cell . ${\displaystyle S}$ ${\displaystyle dim(x)}$ ${\displaystyle x}$ ${\displaystyle x\rho y}$ ${\displaystyle x}$ ${\displaystyle y}$

history

The idea of ​​an abstract cell complex goes back to J. Listing (1862) and E. Steinitz (1908). Also AW Tucker (1933), K. Reidemeister (1938), PS Aleksandrov (1956) and R. Klette and A. Rosenfeld (2004) describe abstract cell complexes. Numerous works on image processing use abstract cell complexes, examples of which are the textbooks by Pavlidis, Rosenfeld and Serra. Kovalevsky proposes an axiomatic theory of locally finite topological spaces as a generalization of abstract cell complexes.

literature

• Tucker: An abstract approach to manifolds
• Burdock: Cell complexes through time

Individual evidence

1. ↑ J. Listing: The Census of Spatial Complexes. In: Treatises of the Royal Society of Sciences in Göttingen. Volume 10, Göttingen 1862, pp. 97-182.
2. ^ E. Steinitz: Contributions to Analysis. In: Report of the meeting of the Berlin Mathematical Society. Volume 7, 1908, pp. 29-49.
3. ^ AW Tucker: An abstract approach to manifolds. In: Annals Mathematics. Volume 34, 1933, pp. 191-243.
4. ↑ K. Reidemeister: Topology of the polyhedra and combinatorial topology of the complexes. Academic Publishing Company, Leipzig 1938.
5. ^ PS Aleksandrov: Combinatorial Topology. Graylock Press, Rochester 1956.
6. ^ R. Klette, A. Rosenfeld: Digital Geometry. Elsevier, 2004.
7. ^ Theodosios Pavlidis: Structural pattern recognition. (Springer Series in Electrophysics, Vol. 1). Springer-Verlag, Berlin / New York 1977, ISBN 3-540-08463-0 .
8. ↑ Azriel Rosenfeld: Picture languages. Formal models for picture recognition. (Computer Science and Applied Mathematics). Academic Press, New York / London, 1979, ISBN 0-12-597340-3 .
9. ↑ J. Serra: Image analysis and mathematical morphology. German version revised by Noel Cressie. Academic Press, London 1984, ISBN 0-12-637240-3 .
10. ↑ http://www.geometry.kovalevsky.de/