Digital Manifolds and the Theorem of Jordan-Brouwer

Publish in

Presentations

13 views

Please download to get full document.

View again

of 34
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
This text developes a theory on how to describe adjacency relations on regular lattices in arbitrary dimensions such that the Theorem of Jordan-Brouwer is satisfied. (The generalisation of the 2-dimensional Jordan-curve theorem)
Tags
Transcript
  Digital Manifolds and the Theorem of Jordan-Brouwer Martin H¨unniger Abstract We give an answer to the question given by T.Y.Kong in his article  Can 3-D Digital Topology be Based on Axiomatically Defined 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 point-set. In this way, one is able todefine the notion of a  ( n − 1 ) -dimensional digital manifold and prove the digitalanalog of the Jordan-Brouwer-Theorem. Contents 1 Introduction 12 Basic Definitions 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 Jordan-Brouwer 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 Jordan-Brouwer 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 thedefinition of a sound topological framework arose. Though in the two dimensionalcase a solution was easy to find, 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 find preconditions so that a discrete analog to thetheorem of Jordan-Brouwer–the generalization of the Jordan curve theorem to arbitrarydimensions–is satisfied. 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 sufficient,since it is possible to embed other settings in these sets and Z n is very suitable in geo-metric terms as Albrecht H¨ubler shows for the 2-dimensional case [5]. The main focusis on the adjacency relations with which we add structure to the Z n . As figure 1 shows,the validity of a discrete “Jordan curve” theorem depends on the adjacency relationswe apply to the points. It is in general not sufficient 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 define a correct discrete notion of a simple closed curve are called “goodpairs”. In this paper we will solve the problem of defining 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 (8-adjacency) or disconnected (4-adjacancy).Also the set of white points may be connected (8-adjacency) or disconnected (4-adjacency).Only 4-adjacency is depicted. The first person to give an idea for the 2-dimensional 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 first 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 adjacency-relations used bythe authors.T.Y. Kong [10] renewed the question of finding a general theory for the problem of topologization of   Z n in 2001. The Approach we a taking is a new definition 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 aredefining a real manifold if and only if the adjacencies on Z n were chosen correctly andthe real version of the Jordan-Brouwer Theorem can be applied.Thepaperisorganizedasfollows: Insection2wegivebasicdefinitionstomakeprecisethe topological and graph theoretic terms. In section 3 we give the definition of a digitalmanifold and study its basic properties. Also we give a new and general definition of a good pair. In section 4 we introduce the Theorem of Jordan-Brouwer. 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 Jordan-Brouwer 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 Definitions First of all, we review some definitions from the field of simplicial complexes. Ourgoal is to construct these objects from subsets of  Z n . 2.1 Simplices and Simplicial Complexes Definition 1  Let x 0 , . . . ,  x k   ∈ R n be affine 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 k-Simplex. Let  σ , τ ⊆ R n be simplices, then  τ  is called  face  of   σ , in terms:  τ ≤ σ , if the vertices of  τ  are also vertices of   σ . The relation  τ  <  σ  means  τ ≤ σ  and  τ  =  σ . Definition 2  A  simplicial complex  K in  R n is a finite 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  non-degenerated , if every  ( n − 2 ) -simplex  σ  is face of exactly two  ( n − 1 ) -simplices. Definition 3  A simplicial complex K is a  combinatorial   ( n − 1 ) -pseudomanifold   with-out border, if 1. K is homogenous  ( n − 1 ) -dimensional,2. K is non-degenerated,3. K is strongly connected. 2.2 Adjacencies To establish structure on the points of the set  Z n we have to define some kind of con-nectivity relation. Definition 4  Given a set   P   , a relation  α  ⊆  P   × P   is called   adjacency  if it has the following properties:1.  α  is finitary:  ∀  p ∈ P   : | α (  p ) | <  ∞ .2.  P   is connected under   α .3. Every finite subset of   P   has at most one infinite 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
Related Search

Previous Document

LAM_Business_Package.pdf

Next Document

Bogota city

We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks