This text developes a theory on how to describe adjacency relations on regular lattices in arbitrary dimensions such that the Theorem of JordanBrouwer is satisfied. (The generalisation of the 2dimensional Jordancurve theorem)
Digital Manifolds and the Theorem of JordanBrouwer
Martin H¨unniger
Abstract
We give an answer to the question given by T.Y.Kong in his article
Can 3D Digital Topology be Based on Axiomatically Deﬁned Digital Spaces?
[10]. In thisarticle he asks the question, if so called “good pairs” of neighborhood relations canbe found on the set
Z
n
such that the existence of digital manifolds of dimension
n
−
1, that separate their complement in exactly two connected sets, is guaranteed.To achieve this, we use a technique developed by M. Khachan et.al. [7]. A setgiven in
Z
n
is translated into a simplicial complex that can be used to study thetopological properties of the srcinal discrete pointset. In this way, one is able todeﬁne the notion of a
(
n
−
1
)
dimensional digital manifold and prove the digitalanalog of the JordanBrouwerTheorem.
Contents
1 Introduction 12 Basic Deﬁnitions 3
2.1 Simplices and Simplicial Complexes . . . . . . . . . . . . . . . . . . 32.2 Adjacencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.3 The Separation Property . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Digital Manifolds 8
3.1 Double Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.2 Degenerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Theorem of JordanBrouwer 12
4.1 The construction of a Simplicial Complex . . . . . . . . . . . . . . . 124.2 The Construction of a Pseudomanifold . . . . . . . . . . . . . . . . . 154.3 Properties of a Digital Manifold . . . . . . . . . . . . . . . . . . . . 17
5 The Proof of the Theorem of JordanBrouwer for Digital Manifolds 19
5.1 The Homogeneity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205.2 The Nondegenerateness . . . . . . . . . . . . . . . . . . . . . . . . . 235.3 The strong connectivity . . . . . . . . . . . . . . . . . . . . . . . . . 261
6 Conclusions 33
1 Introduction
Since the beginning of the research in digital image processing, the question of thedeﬁnition of a sound topological framework arose. Though in the two dimensionalcase a solution was easy to ﬁnd, its generalization to higher dimensions seemed veryhard. This is easy to see from the vast amount of theories under consideration by thecommunity. The central goal was to ﬁnd preconditions so that a discrete analog to thetheorem of JordanBrouwer–the generalization of the Jordan curve theorem to arbitrarydimensions–is satisﬁed. The Jordan curve theorem states that every closed curve in theplane, that is simple, i.e. has no crossings, separates the plane in exactly two regions:Its inside and its outside and is itself the boundary of both of these sets.In this paper, we restrict the discrete setting to lattices
Z
n
for
n
≥
2. This is sufﬁcient,since it is possible to embed other settings in these sets and
Z
n
is very suitable in geometric terms as Albrecht H¨ubler shows for the 2dimensional case [5]. The main focusis on the adjacency relations with which we add structure to the
Z
n
. As ﬁgure 1 shows,the validity of a discrete “Jordan curve” theorem depends on the adjacency relationswe apply to the points. It is in general not sufﬁcient to use the same adjacencies for thewhite and black points, i.e. the background and the foreground, as this picture showsand so we have to deal with pairs of such relations. The pairs of adjacencies that makeit possible to deﬁne a correct discrete notion of a simple closed curve are called “goodpairs”. In this paper we will solve the problem of deﬁning a discrete
(
n
−
1
)
manifoldin
Z
n
, which is the
n
dimensional analog to a simple closed curve, and characterize thegood pairs in all dimensions greater than 2.
Figure 1:
Depending on the adjacency relations we use for the black and the white points,respectively, the set of black points is connected (8adjacency) or disconnected (4adjacancy).Also the set of white points may be connected (8adjacency) or disconnected (4adjacency).Only 4adjacency is depicted.
The ﬁrst person to give an idea for the 2dimensional case was A. Rosenfeld [12] in1973. E. Khalimsky [6] studied very special topological adjacency relations, whichwere suitable in any dimension, during the early 1980s. In the 1990s, G.T. Herman [3]proposed a framework with very general neighborhood relations, he tried to make theJordan curve property to a property of pairs of points. Unfortunately the approach doesnot resemble the intuition given by the Euclidean case. Anyway, the theory showed apromising method, how to generalize the concept of a good pair to higher dimensions.2
Later, in 2003, M. Khachan et al. [7] brought together the theory of pairs of the form
(
2
n
,
3
n
−
1
)
in arbitrary dimensions
n
. They were the ﬁrst ones using the notion of thesimplicial complex, a basic structure known from algebraic topology. This approachled to deeper insights, but it was bound to the very special adjacencyrelations used bythe authors.T.Y. Kong [10] renewed the question of ﬁnding a general theory for the problem of topologization of
Z
n
in 2001. The Approach we a taking is a new deﬁnition of goodpairs in dimensions greater than 2 and a new general concept of a
(
n
−
1
)
manifold in
Z
n
. For a given
(
n
−
1
)
manifold
M
in
Z
n
we are able to construct a simplicial complex
K
(
M
)
, that preserves the topological properties of
M
, if
Z
n
is endowed with a goodpair of adjacencies. The complex
K
(
M
)
then has nice topological properties–it is a socalled Pseudomanifold (as studied by P.S. Alexandrov [1]) and therefore, we are ableto embed it in
n
dimensional Euclidean space in a natural way. By doing this we aredeﬁning a real manifold if and only if the adjacencies on
Z
n
were chosen correctly andthe real version of the JordanBrouwer Theorem can be applied.Thepaperisorganizedasfollows: Insection2wegivebasicdeﬁnitionstomakeprecisethe topological and graph theoretic terms. In section 3 we give the deﬁnition of a digitalmanifold and study its basic properties. Also we give a new and general deﬁnition of a good pair. In section 4 we introduce the Theorem of JordanBrouwer. Together withthe notions of digital manifolds and good pairs, we are able to construct a simplicialcomplex with the same topological properties as the digital manifold. Having this toolsestablished, we can give the general proof of the discrete variant of the Theorem of JordanBrouwer in arbitrary dimensions in section 5. The proof consists of three parts,all involving heavy case differentiations of technical nature. We end the paper withConclusions in section 6.
2 Basic Deﬁnitions
First of all, we review some deﬁnitions from the ﬁeld of simplicial complexes. Ourgoal is to construct these objects from subsets of
Z
n
.
2.1 Simplices and Simplicial Complexes
Deﬁnition 1
Let x
0
, . . . ,
x
k
∈
R
n
be afﬁne independent points. The set
σ
=
{
x
∈
R
n
:
x
=
k
∑
i
=
0
λ
i
x
i
with
k
∑
i
=
0
λ
i
=
1
,
λ
0
, . . . ,
λ
q
>
0
}⊆
R
n
(1)
is the (open)
simplex with vertices
x
0
, . . . ,
x
k
. We also write
σ
= (
x
0
, . . . ,
x
k
)
. Thenumber k is the dimension of
σ
. Sometimes, for brevity, we call
σ
just kSimplex.
Let
σ
,
τ
⊆
R
n
be simplices, then
τ
is called
face
of
σ
, in terms:
τ
≤
σ
, if the vertices of
τ
are also vertices of
σ
. The relation
τ
<
σ
means
τ
≤
σ
and
τ
=
σ
.
Deﬁnition 2
A
simplicial complex
K in
R
n
is a ﬁnite set of simplices in
R
n
with the following properties
3
1. For any
σ
∈
K and
τ
<
σ
is
τ
∈
K.2. For any
σ
,
τ
∈
K with
σ
=
τ
holds
σ
∩
τ
=
/0
Let
K
be a simplicial complex in
R
n
. The geometric realization of
K
is the set
σ
∈
K
σ
⊆
R
n
.
(2)A simplicial complex
K
is
homogenous
(
n
−
1
)
dimensional
, if every simplex in
K
isface of a
(
n
−
1
)
simplex in
K
. A homogenous
(
n
−
1
)
dimensional simplicial complex
K
is
strongly connected
, if for any two
(
n
−
1
)
simplices
σ
and
σ
exists a sequence of
(
n
−
1
)
simplices
σ
=
σ
0
, . . . ,
σ
l
=
σ
, such that
σ
i
and
σ
i
+
1
share a common
(
n
−
2
)
face for every
i
∈{
0
, . . . ,
l
−
1
}
. The complex
K
is
nondegenerated
, if every
(
n
−
2
)
simplex
σ
is face of exactly two
(
n
−
1
)
simplices.
Deﬁnition 3
A simplicial complex K is a
combinatorial
(
n
−
1
)
pseudomanifold
without border, if 1. K is homogenous
(
n
−
1
)
dimensional,2. K is nondegenerated,3. K is strongly connected.
2.2 Adjacencies
To establish structure on the points of the set
Z
n
we have to deﬁne some kind of connectivity relation.
Deﬁnition 4
Given a set
P
, a relation
α
⊆
P
×
P
is called
adjacency
if it has the following properties:1.
α
is ﬁnitary:
∀
p
∈
P
:

α
(
p
)

<
∞
.2.
P
is connected under
α
.3. Every ﬁnite subset of
P
has at most one inﬁnite connected component as com plement.
A set
M
⊆
P
is called
connected
if for any two points
p
,
q
in
M
exist points
p
0
, . . . ,
p
m
andapositiveinteger
m
suchthat
p
0
=
p
,
p
m
=
q
and
p
i
+
1
∈
A
(
p
i
)
forall
i
∈{
0
, . . . ,
m
−
1
}
.In the text we will consider pairs
(
α
,
β
)
of adjacencies on the set
Z
n
. In this pair
α
represents the adjacency on a set
M
⊆
Z
n
, while
β
represents the adjacency on
M
c
=
Z
n
\
M
.Let
T
be the set of all translations on the set
Z
n
. The generators
τ
1
, . . . ,
τ
n
∈
T
of
Z
n
induce a adjacency
π
in a natural way:4