Abstrakter Zellkomplex
# Abstrakter Zellkomplex

In der Mathematik ist ein abstrakter Zellkomplex (auch abstrakter Zellenkomplex) eine abstrakte Menge von „Zellen“ mit einer Binärrelation („enthalten im Abschluss von“) und einer Abbildung in die nichtnegativen ganzen Zahlen („Dimension“). Der Komplex heißt „abstrakt“, weil die „Zellen“ keine Teilmengen eines euklidischen Raumes sind, wie dies bei Simplizialkomplexen oder CW-Komplexen der Fall ist. Abstrakte Zellkomplexe spielen eine wichtige Rolle in der Bildanalyse und in der Computergrafik.

## Motivation

In der Topologie verwendet man häufig (geometrische) Zellkomplexe, die aus (offenen oder abgeschlossenen) Zellen zusammengesetzt sind, d. h. Unterräumen homöomorph zu (offenen oder abgeschlossenen) Kugeln im euklidischen Raum. Meist wird vorausgesetzt, dass es sich um einen CW-Komplex handelt. (Ein noch speziellerer Begriff sind Simplizialkomplexe.) Unter anderem für Anwendungen in der Bildverarbeitung ist es aber nützlich, statt geometrischer Zellkomplexe abstrakt definierte Zellkomplexe zu verwenden.

## Definition

Ein abstrakter Zellkomplex $K=(S,\rho ,dim)$ ist gegeben durch

* eine Menge $S$,
* eine binäre Relation $\rho$ auf $S$,
* eine Funktion $dim:S\rightarrow \mathbb {N} \cup \left\{0\right\}$,

welche folgende Axiome erfüllen:

* aus $x\rho y$ und $y\rho z$ folgt $x\rho z$,
* aus $x\rho y$ folgt $dim(x)<dim(y)$.

In der Regel wird nach Tucker noch folgendes weiteres Axiom vorausgesetzt:

* Wenn $x\rho z$ und $dim(z)-dim(x)>1$, dann gibt es ein $y\in S$ mit $x\rho y$ und $y\rho z$.

Verschiedene Autoren verwenden noch zusätzliche weitere Axiome.

Elemente von $S$ werden als Zellen bezeichnet. Im Spezialfall eines geometrischen Zellkomplexes ist $dim(x)$ die Dimension der Zelle $x$ und $x\rho y$ bedeutet, dass die Zelle $x$ im Abschluss der Zelle $y$ liegt.

## Geschichte

Die Idee eines abstrakten Zellkomplexes geht auf J. Listing (1862) und E. Steinitz (1908) zurück. Auch A. W. Tucker (1933), K. Reidemeister (1938), P. S. Aleksandrov (1956) sowie R. Klette und A. Rosenfeld (2004) beschreiben abstrakte Zellkomplexe. Zahlreiche Arbeiten zur Bildverarbeitung verwenden abstrakte Zellkomplexe, Beispiele dafür sind die Lehrbücher von Pavlidis, Rosenfeld und Serra. Bei Kovalevsky wird eine axiomatische Theorie der lokal endlichen topologischen Räume als Verallgemeinerung der abstrakten Zellkomplexe vorgeschlagen. In Kovalevsky werden effiziente Algorithmen mit Verwendung der abstrakten Zellkomplexe für die Verfolgung, Codierung und Polygonisierung von Begrenzungen, wie auch für die Kantendetektion beschrieben.

