### Paper Menu >>

### Journal Menu >>

Applied Mathematics, 2010, 1, 377-386 doi:10.4236/am.2010.15050 Published Online November 2010 (http://www.SciRP.org/journal/am) Copyright © 2010 SciRes. AM Continuous Maps on Digital Simple Closed Curves Laurence Boxer1,2 1Department of Computer and Information Sciences, Niagara University, New York, USA 2Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, USA E-mail: boxer@niagara.edu Received August 2, 2010; revised September 14, 2010; accepted September 16, 2010 Abstract We give digital analogues of classical theorems of topology for continuous functions defined on spheres, for digital simple closed curves. In particular, we show the following: 1) A digital simple closed curve S of more than 4 points is not contractible, i.e., its identity map is not nullhomotopic in S; 2) Let X and Y be digital simple closed curves, each symmetric with respect to the origin, such that 5|>| Y (where || Y is the number of points in Y). Let YXf : be a digitally continuous antipodal map. Then f is not nullho- motopic in Y; 3) Let S be a digital simple closed curve that is symmetric with respect to the origin. Let ZSf : be a digitally continuous map. Then there is a pair of antipodes Sxx },{ such that 1|)()(| xfxf . Keywords: Digital Image, Digital Topology, Homotopy, Antipodal Point 1. Introduction A digital image is a set X of lattice points that model a “continuous object” Y, where Y is a subset of a Eucli- dean space. Digital topology is concerned with deve- loping a mathematical theory of such discrete objects so that, as much as possible, digital images have topological properties that mirror those of the Euclidean objects they model; however, in digital topology we view a digital image as a graph, rather than, e.g., a metric space, as the latter would, for a finite digital image, result in a discrete topological space. Therefore, the reader is reminded that in digital topology, our “nearness” notion is the graphical notion of adjacency, rather than a neighborhood system as in classical topology; usually, we use one of the na- tural l c-adjacencies (see Section 2). Early papers in the field, e.g., [1-8], noted that this notion of nearness allows us to express notions borrowed from classical topology, e.g., connectedness, continuous function, homotopy, and fundamental group, such that these often mirror their analogs with respect to Euclidean objects modeled by respective digital images. Applications of digital topo- logy have been found shape description and in image processing operations such as thinning and skeletoni- zation [9]. A. Rosenfeld wrote the following: “The discrete grid (of pixels or voxels) used in digital topology can be regarded as a ‘digitization’ of (two or three-dimensional) Euclidean space; from this viewpoint, it is of interest to study conditions under which this digitization process preserves topological (or other geometric) properties” [3]. In this spirit, we obtain in this paper several properties of continuous maps on digital simple closed curves, inspired by analogs for Euclidean simple closed curves. In particular, we show that digital simple closed curves of more than 4 points are not contractible, and we obtain several results for continuous maps and antipodal points on digital simple closed curves. 2. Preliminaries Let Z be the set of integers. Then d Z is the set of lattice points in d-dimensional Euclidean space. Let d Z X and let be some adjacency relation for the members of X . Then the pair ),( X is said to be a (binary) digital image. A variety of adjacency relations are used in the study of digital images. Well known adjacencies include the following. For a positive integer l with 1ld and two distinct points 12 12 =(,,, ), =(,,,), d dd ppppqqqqZ p and q are l c-adjacent [10] if • there are at most l indices i such that 1|=| ii qp , and • for all other indices j such that 1|| jjqp , jj qp =. See Figure 1. L. BOXER Copyright © 2010 SciRes. AM 378 Figure 1. In 2 Z , each of the points 1= (1,0)p and 2= (0,1)p is both 1 c-adjacent and 2 c-adjacent to 0= (0,0)p, since both 1 p and 2 p differ from 0 p by 1 in exactly one coordinate and coincide in the other coordinate; 3=(-1,1)p is 2 c-adjacent, but not 1 c-adjacent, to 0 p, since 0 p and 3 p differ by 1 in both coordinates. The notation l c is sometimes also understood as the number of points d Zq that are l c-adjacent to a given point d Zp . Thus, in Z we have 2= 1 c; in 2 Z we have 4= 1 c and 8= 2 c; in 3 Z we have 18,=6,= 21 cc and 26= 3 c. More general adjacency relations are studied in [11]. Let be an adjacency relation defined on d Z . A - neighbor of a lattice point p is -adjacent to p. A digital image d Z X is -connected [11] if and only if for every pair of different points Xyx ,, there is a set },,,{ 10 r xxx of points of a digital image X such that r xyxx =,= 0 and i x and 1i x are -neighbors where 1},{0,1, ri . Let Zba , with ba<. A digital interval [7] is a set of the form }.|{=],[ bzaZzba Z Let 0 d Z X and 1 d Z Y be digital images with 0 -adjacency and 1 -adjacency respectively. A function YXf : is said to be ),( 10 -continuous [2,8], if for every 0 -connected subset U of X , )(Uf is a 1 -connected subset of Y . We say that such a function is digitally continuous. Proposition 2.1 [2,8] Let 0 d Z X and 1 d Z Y be digital images with 0 -adjacency and 1 -adjacency respectively. Then the function YXf : is ),(10 - continuous if and only if for every 0 -adjacent points },{10 xx of X , either )(=)( 10 xfxf or )(0 xf and )( 1 xf are 1 -adjacent in Y . This characterization of continuity is what is called an immersion, gradually varied operator, or gradually varied mapping in [12,13]. Given digital images ),( ii X , {0,1}i, suppose there is a ),( 10 -continuous bijection 10 :XXf such that 01 1:XXf is ),( 01 -continuous. We say 0 X and 1 X are ),(10 -isomorphic [14] (this was called ),( 10 -homeomorphic in [7]) and f is a ),( 10 -isomorphism (respectively, a ),( 10 -homeo- morphism). By a digital -path from x to y in a digital image X , we mean a )(2, -continuous function Xmf Z][0,: such that xf =(0) and ymf=)( . We say m is the length of this path. A simple closed -curve of 4m points (for some adjacencies, the minimal value of m may be greater than 4; see below) in a digital image X is a sequence {(0), (1),,ff (1)}fm of images of the -path :[0, 1] Z fm X such that )(if and )( jf are -adjacent if and only if mij mod1)(= . If 1 0= }{=m ii xS where )(= ifx i for all Z mi 1][0, , we say the points of S are circularly ordered. Digital simple closed curves are often examples of digital images d Z X for which it is desirable to consider XZ d\ as a digital image with some adja- cency (not necessarily the same adjacency as used by X ). For example, by analogy with Euclidean topology, it is desirable that a digital simple closed curve 2 Z X satisfy the “Jordan curve property” of separating 2 Z into two connected components (one “inside” and the other “outside” X ). An example that fails to satisfy this property [10] if we allow 4|=| X is given by ),(1 cX , where (0,1)}(1,1),(1,0),{(0,0), = X is circularly ordered, and ),\(2 2cXZ is 2 c-connected. However, this anomaly is essentially due to the “small- ness” of X as a simple closed curve; it is known [1,15,16] that for 8= 1 m and 4= 2 m, if 2 Z X is a digital simple closed i c-curve such that i mX|| , then XZ \ 2 has exactly 2 i c3-connected components, {1,2} i. Thus, it is customary to require that a digital simple closed curve 2 Z X satisfy 8|| X when 1 c- adjacency is used; 4|| X when 2 c-adjacency is used. Let 0 d Z X and 1 d Z Y be digital images with 0 -adjacency and 1 -adjacency respectively. Two ),( 10 -continuous functions YXgf :, are said to be digitally ),(10 -homotopic in Y [8] if there is a positive integer m and a function YmXH Z ][0,: such that • for all Xx , )(=,0)( xfxH and )(=),( xgmxH; • for all Xx , the induced function:[0, ] x Z H m Y defined by ,][0,),(=)( Zx mtallfortxHtH is )(2, 1 -continuous; and • for all Z mt ][0, , the induced function YXHt: defined by ,),(=)( XxallfortxHxHt is ),( 10 -continuous. We say that the function H is a digital ),( 10 - homotopy between f and g . L. BOXER Copyright © 2010 SciRes. AM 379 Additional terminology associated with homotopic maps includes the following. • If g is a constant map, we say f is ),( 10 - nullhomotopic [8]; if, further, ),(=),( 10 YX and X f1= (the identity map on X ), we say X is 0 - contractible [7,17]. • If )(=),( 00 xftxH for some Xx 0 and all Z mt ][0,, we say H is a ),( 10 -pointed homotopy [18]. • If YmmHZZ ][0,][0,: 10 is a ),( 1 c-homotopy between ),( 1 c-continuous functions Ymgf Z][0,:, 0 such that for all Z mt ][0, 1 , (0)=(0)=)(0, gftH and )(=)(=),( 000 mgmftmH , we say H holds the endpoints fixed [18]. Proposition 2.2 [8] Suppose YXff :, 10 are ),( -continuous and ),( -homotopic. Suppose ZYgg:, 10 are ),( -continuous and ),( -ho- motopic. Then 00 fg and 11 fg are (,) -homo- topic in Z . 3. Homotopy Properties of Digital Simple Closed Curves A classical theorem of Euclidean topology, due to L.E.J. Brouwer, states that a d-dimensional sphere d S is not contractible [19]. Theorem 3.3, below, is a digital analog, for 1=d. We also present some related results in this section. Proposition 3.1 Let a S be a digital simple closed a -curve, {0,1}a. Let 10 :SSf be a ),( 10 - continuous function. If ||=|| 10 SS , then the following are equivalent. a) f is one-to-one. b) f is onto. c) f is a ),( 10 -isomorphism. Proof: Since ||=|| 10 SS , the equivalence of a) and b) follows from the fact that 0 S is a finite set. That c) implies both a) and b) follows from the definition of isomorphism. Therefore, we can complete the proof by showing that b) implies c). Let 1 0=,}{=n iiaa xS, where the points of a S are circu- larly ordered, {0,1}a. Let 11, Sx u and let )(= 1, 1 0, uv xfx . Then the 1 -neighbors of u x1, in 1 S are nu xmod1)(1, and nu xmod1)(1, , and the 0 -neighbors of v x0, in 0 S are nv xmod1)(0, and nv xmod1)(0,. Since f is a continuous bijection, our choice of v x0, implies 0,(1) mod0,(1) mod1,(1) mod1,(1) mod {,} = {,}. vnvn unun fx xx x Thus, 1 1,(1) mod1,(1) mod0,(1) mod0,(1) mod {,} = {,}. unun vnvn fx xx x Since u was taken as an arbitrary index, 1 f is ),( 01 -continuous, so f is a ),( 10 -isomorphism. Theorem 3.2 Let S be a simple closed -curve and let SmSH Z ][0,: be a ),( -homotopy between an isomorphism 0 H and =, m H fwhere SSf )( . Then 4|=| S. Proof: Let 1 0= }{=n ii xS , where the points of S are circularly ordered. There exists Z mw ][1, such that }.)(|][0,{min = SSHmtw tZ Without loss of generality, )( 1SHx w . Then the induced function 1w H is a bijection, so there exists Sxu such that 1 =1),( xwxH u . By Proposition 3.1, },{=}),({ 20mod1)(mod1)(1 xxxxH nunuw , and the continuity property of homotopy implies },{),( 20xxwxH u . Without loss of generality, (1)mod 0 ,1= un H xwx (1) and 2 ,=. u H xw x (2) Suppose 4>n. Equation (2) implies },,{),( 321mod1)( xxxwxH nu , but this is impossible, for the following reasons. • 1mod1)(),( xwxHnu , by choice of 1 x. • },{),( 32mod1)(xxwxH nu , from Equation (1), because 4>n implies neither 2 x nor 3 x is -adjacent to 0 x. The contradiction arose from the assumption that 4>n. Therefore, we must have 4n. Since a digital simple closed curve is assumed to have at least 4 points, we must have 4=n. In [8], an example is given of a simple closed 2 c- curve 2 ZS such that SZ \ 2 has 2 1 c-connected components, with 4|=| S, such that S is 2 c-contrac- tible (see Figure 2). By contrast, we have the following. Theorem 3.3 Let ),( S be a simple closed -curve such that 4|>| S. Then S is not -contractible. Proof: It follows from Theorem 3.2 that if 4|>| S, then there cannot be a ),( -homotopy between S 1 and a constant map in S. It is natural to ask whether we can obtain an analog of Theorem 3.3 for higher dimensions. In order to do so, we must decide what is an appropriate digital model for the k-dimensional Euclidean sphere k S. The literature contains the following. • Let k X2 be the set of all points k Zp such that p is a 1 c-neighbor of the origin. Then ([10], Proposition 4.1) k X2 is k c-contractible. Notice that this example generalizes the contractibility of a 4-point digital simple closed curve [8] (see Figure 2 for the planar version); the contractibility seems due to the smallness of the image, rather than its form. • Let k IBd denote the boundary of a digital k-cube, i.e., for some integer 2>n, 1 = {(,,)[0,1]|{1,,}, {0, 1}}. k kkZ i Bd Ixxnfor some ik xn L. BOXER Copyright © 2010 SciRes. AM 380 Figure 2. 2 c-contraction of 4 X , a digital simple closed 2 c-curve, via 44 ×[0,2]Z H:XX. (a) shows 4 X . Points are labeled by indices. We have (,0)=Hx x for all 4 x X . Arrows show the “motion” of 23 , x x at the next step. (b) shows the results of the first step of the contraction: 030 (,1) =,1) =Hx H(x x; 121 ( ,1)( ,1)Hx =Hx =x . The arrow shows the motion at the next step of the contraction. (c) shows the results of the final step of the contraction: 0 (2) i Hx, =x for all {0,1, 2, 3}i. See Figure 3 for the planar version. Then ([7], Coro- llary 5.9) for >2n, k B dI is not 1 c-contractible. The next result may be interpreted as stating that for 4>n, a map homotopic to S 1 must be a “rotation” of the points of S. Theorem 3.4 Let S be a simple closed -curve such that 4>|=| nS . Let SSf : be a ),( - continuous function such that f is ),( -homotopic to S 1. Then, for some integer j, we have .1][0, = )(mod)(Znjii niallforxxf Proof: Let SmSH Z][0,: be a ),( -homo- topy from S 1 to f. For Z mt ][0, , let SSHt: be the induced map. The assertion follows from the following. Claim 1: For each Z mt ][0,, there is an integer j such that njiit xxH mod)( =)( for all Z ni 1][0,. To prove Claim 1, we argue by mathematical induc- tion on t . For 0=t, we can clearly take 0=j. Now, suppose the claim is valid for Z ut ][0, such that mu <0 . Then, in particular, there is an integer j such that njiiu xxH mod)( =)( for all Z ni 1][0,. The continuity properties of homotopy imply 10 () u Hx ( 1)mod( 1)mod {,, } j nj jn xxx . Without loss of generality, juxxH =)(01. This is the initial case of the following: Claim 2: njkku xxH mod)(1 =)( for all Z nk 1][0, . Suppose the equation of Claim 2 is true for all Z vk ][0,, for some Z nv 2][0, . In particular, .=)(mod)(1 njvvu xxH (3) By the continuity properties of homotopy, )( 11 vu xH is adjacent to or coincides with njvvuxxH mod)(1 =)( and with 1(1)mod ()= . uvv jn Hxx Thus, 11 ()mod (){ , uv vjn Hxx (1)mod } vj n x . Since 1u H must also be an isomorphism by Theorem 3.2, from Equation (3), 11 ()= uv Hx (1)modvj n x . This completes the induction proof for the Claim 2, which, in turn, completes the induction proof for the Claim 1. Thus, the assertion is established. 4. Antipodal Maps A classical theorem of Euclidean topology, due to K. Borsuk, states that a continuous antipodal map:d f S d S from the d-dimensional unit sphere to itself is not homotopic to a constant map [19]. In this section, we obtain a digital analog, Theorem 4.16, for 1=d. We say a set d Z X is symmetric with respect to the origin if X satisfies the property that .XxifonlyandifXx Suppose we have 0 d X Z, 1 d YZ, and X is sym- metric with respect to the origin. A function : f XY is called antipodal-preserving or an Figure 3. 2 B dI , the “boundary” of a digital square. L. BOXER Copyright © 2010 SciRes. AM 381 Figure 4. A digital simple closed 1 c-curve 7 =0 ={ } ii Sx and a 11 (,)cc-continuous map : f SS such that f is 11 (,)cc -homotopic to 1S. According to Theorem 3.4, such a map f must “rotate” the members of S. In (a), points of S are labeled by indices. In (b), each yS is labeled by the index of the point i x S such that ()= i f xy. Here, we have (2)mod8 ()= ii fx x for all i. antipodal map if )(=)( xfxf for all Xx [19]. In this section, we study properties of continuous antipodal maps between digital simple closed curves. Lemma 4.1 Let 10,pp be l c-adjacent points in d Z , dl 1. Then 0 p and 1 p are not antipodal. Proof: The hypothesis implies that there is an index i such that 0 p and 1 p differ by 1 in the th i coordinate: 1|=| 1,0, iipp. If 0 p and 1 p are antipodal, this would imply 1/2,1/2}{=},{ 1,0, ii pp , which is impossible. Lemma 4.2 Let 10,pp be l c-adjacent points in d Z , dl 1. Then 0 p and 1 p are l c-adjacent. Proof: Elementary, and left to the reader. Lemma 4.3 Let 1 0= }{=n ii xS be a digital simple closed l c-curve in d Z such that the points of S are cir- cularly ordered. If S is symmetric with respect to the origin, then the origin is not a member of S. Proof: Suppose the origin is a member of S. Without loss of generality, 0 x is the origin, and therefore is its own antipode. By Lemma 4.2, 1 x and 1n x are antipodes; by Lemma 4.1, these points are not l c-adjacent. This establishes the base case of an induction argument: 1 1= 1 0=1 }{}{=jjnii xxS is a connected subset of S, such that 1 x and 1n x are non-adjacent antipodes; hence, 1 S is ),(1 ccl-isomorphic to a digital interval. Now, suppose for some integer k, 1)/2(<1 nk , k jjn k iik xxS 1=0= }{}{= is ),(1 ccl-isomorphic to a digital interval, with endpoints k x and kn x, such that m x and mn x are non-adjacent antipodes for all },{1, km. Then, by Lemma 4.2, 1k x and 1kn x are antipodes, and by Lemma 4.1, these points are not l c-adjacent. Thus, 1 1= 1 0=1 }{}{= k jjn k iik xxS is ),(1 ccl- isomorphic to a digital interval, with endpoints 1 x and 1n x. This completes an induction argument from which we conclude that 1 1)/2(= 1)/2( 0= }{}{ = n nni i n ii xxS is ),(1 ccl-isomorphic to a digital arc, with the endpoints of S being 1)/2(n x and 1)/2(nn x, such that 1)/2(1 ni implies i x and in x are non-adjacent antipodes. • If n is odd, then 1 n is even, so SS = . This is a contradiction, since S is not a simple closed l c- curve. • If n is even, then }{\= /2n xSS. Since S is symmetric with respect to the origin, we must have that /2n x is the origin. But since S is a simple closed l c-curve in which 0 x is the origin, this is a contra- diction. Whether n is even or odd, the assumption that the origin belongs to S yields a contradiction. Hence, the origin is not a member of S. Lemma 4.4 Let 1 0= }{=n ii xS be a digital simple closed l c-curve in d Z such that the points of S are circularly ordered. If S is symmetric with respect to the origin, then n is even. Proof: By Lemma 4.3, the origin is not a member of S, so every member of S is distinct from its antipode. Therefore, n must be even. Lemma 4.5 Let 1 0= }{=n ii xS be a digital simple closed l c-curve in d Z such that the points of S are cir- cularly ordered. If S is symmetric with respect to the origin, then for all i we have nniixx mod/2)( = . Proof: Suppose there is a simple closed l c-curve 1 0= }{=n ii xS that is symmetric with respect to the origin such that the points of S are circularly ordered, such that there exist indices vu, such that u x and v x are antipodes and nnuv mod/2)( . Without loss of generality, we can assume 0=u, /2nv . Then, from Lemma 4.2, 1 x is antipodal to either 1v x or nv xmod1)( . Without loss of generality, 1 x and 1v x are antipodal. If 1=1 v, this is a contradiction of Lemma 4.3; or, if 2=1 v, this is a contradiction of Lemma 4.1; otherwise, we inductively repeat the argument above with the antipodal (by Lemma 4.2) pair ),( 22v xx , etc., until similarly we obtain a contradiction of Lemma 4.3 or of Lemma 4.1. The assertion follows. We have the following. Theorem 4.6 Let i d iZS be simple closed i -curves, {0,1} i, each symmetric with respect to the origin. Let 10 :SSf be a ),( 10 -continuous antipodal map. Then f is onto. Proof: Let 1 0=1 }{=n ii xS , where the points of 1 S are circularly ordered. Without loss of generality, there exists 0 Sp such that 0 =)( xpf . Since f is anti- L. BOXER Copyright © 2010 SciRes. AM 382 podal, it follows from Lemma 4.5 that /2 =)( n xpf. Since f is continuous and 0 S is 0 -connected, it follows that one of the 1 -paths in 1 S from 0 x to /2n x is contained in )( 0 Sf . Without loss of generality, )(}{ 0 /2 0= Sfx n jj. For njn <</2 , there exists 0 Sq such that /2 =)( nj xqf , and from Lemma 4.5, /2 0 = = () = ()()(). jjn xx fq s incefis antipodalfqfS Thus, 10 =)( SSf . Corollary 4.7 Let i d iZS be simple closed i - curves, {0,1}i, each symmetric with respect to the origin. Let 10 :SSf be a ),( 10 -continuous anti- podal map. If ||=|| 10 SS , then f is a ),( -iso- morphism. Proof: By Theorem 4.6, f is onto. The assertion follows from Proposition 3.1. Proposition 4.8 Let 1 0= }{= X n ii xX be a simple closed X -curve with circularly ordered points. Let=Y 1 =0 {} nY ii y be a simple closed Y -curve with circularly ordered points. Suppose YmXH Z ][0,: is a ),( YX -homotopy between the ),( YX -continuous maps m HH , 0 such that )(=)(000 xHxHm. Then there is a ),(YX -homotopy :[0,] Z GX m Y between 0 H and m H such that0 (,)=Gxt 00 () H x for all Z mt ][0, Proof: Without loss of generality, 000 =)( yxH . Let ZZ mma ][0,][0,: be defined by ita =)( if i ytxH =),(0. Let YmXG Z][0,: be defined by .=),(, = ),(mod)]([ ji Y ntaji ytxHifytxG Roughly, we may think of ),( txGi as rotating ),(txH i counter to the rotation of ),(0txH , so that the image under G of 0 x at time t is constant with respect to t . We show below that G is a homotopy. In particular, 0=)(=(0) maa , so 00 =HG and mm HG =; and, for all Z mt ][0,, 0[()()]mod0 (,) = = . at atn Y Gx tyy For each Xxi and Z mt ][0, , if jit yxH =)( then we have the following. • By the continuity of t H, we have ( 1)mod(1)mod(1)mod(1)mod ({,}) {, ,}. tin injnjjn XXY Y Hx xyyy Therefore, [()]mod ()= tijatn Y Gx y and 1mod1mod 1 modmod1 mod , ,, . tini n XX jatn jatn jatn YY Y Gxx yyy Therefore, t G is ),( YX -continuous. • Let YmG Z i x][0,: be the induced function de- fined by ),(=)(txGtG i i x. To simplify the following, let 10 (1)=( )=( ), x ii i GHxHx 1 (1)= ()=(), x mi mi i GmH xHx 1)(=)(=0=(0)=1)( mamaaa . Note that the con- tinuity of 0 x H implies that {(1),(1)}{()1,( ),( )1}.atatatat at Suppose jit yxH =)(, so [()]mod ()= x jat n iY Gty . If 1)(=1)( tata , then [(1)]mod [()1]mod (1)== x jat njatn iYY Gt yy is Y -adjacent to () xi Gt . If )(=1)( tata , then )(=1)( tGtG i x i x. If 1)(=1)( tata , then [(1)]mod [()1]mod (1)== x jat njatn iYY Gt yy is Y -adjacent to )(tGi x. Similarly, 1)( tGi x is Y -adjacent to, or equal to, (). xi GtTherefore, the induced function i x G is ),( 1Y c - continuous. Therefore, G is a homotopy between 0 H and m H such that )(=),( 000 xHtxG for all Z mt ][0,. Let ),( X X and ),(Y Y be digital images and let Yy . We denote by : y XY (or, for short, y ) the constant map ()=yx y for all Xx . Lemma 4.9 Let ),( X X and ),( Y Y be digital simple closed curves and let YXf : be ),( YX - homotopic to a constant map. Then for any Xx 0, ))(,(),(:00 xfYxXf is ),( YX -pointed homotopic to the constant map )( 0 xf . Proof: Let YmXF Z ][0,: 0 be a ),(YX - homotopy between f and the constant map 0 y for some Yy 0. Since Y is Y -connected, there is a path Ymp Z][0,:1 from 0 y to )( 0 xf . Then the map YmmXH Z ][0,: 10 defined by ,)( ;0),( =),( 1000 0 mmtmifmtp mtiftxF txH is a homotopy between f and )(0 xf . The assertion follows from Proposition 4.8. Given a digital image ),( X and a positive integer n, for Xx we define [20] (, )= {} {| }. Nxn x yXthereisapath inX f romytoxoflength at mostn The covering space and the lifting of maps are notions borrowed from algebraic topology that have been important in digital algebraic topology. We have the following. Definition 4.10 [20] Let ),( E E and ),( B B be digital images. Let BEp : be a ),( BE -conti- nuous function. Suppose for each Bb there exists N such that L. BOXER Copyright © 2010 SciRes. AM 383 • for some N and some index set M , );(),(=)),(( 11 bpewitheNbNpii E Mi B • if Mji ,, ji , then =),(),( j E i EeNeN ; and • the restriction map ),(),(:| ),( bNeNp B i Ei e E N is a ),( BE -isomorphism for all Mi . Then the map p is a ),( BE - covering map, and the pair ),( pE is a ),( BE - covering (or covering space). The following is a somewhat simpler characterization of the digital covering than given in Definition 4.10. Theorem 4.11 [14] Let ),( E E and ),(B B be digital images. Let BEp : be a ),( BE - continuous function. Then the map p is a ),( BE - covering map if and only if for each Bb , there is an index set M such that • ,1)(=,1))(( 1 i E Mi BeNbNp , with )( 1bpei ; • if Mji ,, ji , then =,1)(,1)( j E i EeNeN ; and • the restriction map ,1)(,1)(:|,1)( bNeNpB i Ei e E N is a ),( BE -isomorphism for all Mi . The following is a minor generalization of an example of a digital covering map given in [20]. Example 4.12 Let dm ii ZcC 1 0= }{= be a circularly ordered simple closed -curve. Let CZp : be defined by mzzp mod=)( for all Z z . Then p is a ),( 1 c-covering map (see Figure 5). Definition 4.13 [20] For digital images ),( E E , ),( B B , and ),( X X , let BEp : be a ),( BE covering map, and let BXf: be ),( BX - continuous. A lifting of f with respect to p is a ),( EX -continuous function EXF : such that fFp =. See Figure 6 for an illustration of Definition 4.13. Theorem 4.14 [20] Let ),( E E be a digital image and Ee 0. Let ),(B B be a digital image and Bb 0. Let BEp: be a ),( BE -covering map such that 00 =)( bep. Then a B -path BmfZ][0,: beginning at 0 b has a unique lifting with respect to p to a path f ~ in E starting at 0 e. For a positive integer n, a ),( BE -covering map BEp : is called a radius n local isomorphism [21] if for each Bb and 1(),epb (,) | N en E p (,) B Nbn is an isomorphism. It was observed in [14] that every covering is a radius 1 local isomorphism, but there are coverings that are not radius 2 local isomor- phisms. Theorem 4.15 [21] Let ),( E E be a digital image and Ee 0. Let ),(B B be a digital image and Bb 0. Let BEp : be a ),(BE -covering map such that 00 =)( bep . Suppose p is a radius 2 local isomorphism. For E -paths Emgg Z][0,:, 10 that start at 0 e, if there is a B -homotopy in B from 0 gp to 1 gp that holds the endpoints fixed, then )(=)( 10 mgmg , and there is a E -homotopy in E from 0 g to 1 g that holds the endpoints fixed. Theorem 4.16 Let 1 0= }{= X n ii xX be a simple closed X -curve with points circularly ordered, that is symmetric with respect to the origin. Let 1 0= }{= Y n ii yY be a simple closed Y -curve with points circularly ordered, that is symmetric with respect to the origin. Let YXf : be a ),( YX -continuous antipodal map. If 5|>| Y, then f is not ),( 10 -nullhomotopic. Proof: Suppose there is such a function f that is ),( 10 -nullhomotopic. From Lemma 4.9, f is point- ed homotopic to )( 0 xf . Let Xnb ZX ][0,: be defined by X nt xtb mod =)( . Let YZp : be the ),( 1Y c -covering map defined by Y nz yzp mod =)( (see Example 4.12). By Proposition 2.2, bf and bxf)( 0 are ),( 1Y c -homotopic paths in Y . From Theorem 4.14, these functions have unique Figure 5. A simple closed 1 c-curve C and a covering by the digital line Z . Members of C are labeled by their respective indices. A point zZ is labeled by the index of point of C to which the covering map sends z. L. BOXER Copyright © 2010 SciRes. AM 384 Figure 6. Example of lifting. 5 =0 ={ } ii Bb is a simple closed 2 c-curve whose members are labeled by their indices. =EZ has its points z labeled above by their coordinates and labeled below by the index i such that ()=i p zb (note p is given by the formula mod 6 ()=z pz b). 11 =0 ={ } mm Xx is a simple closed 2 c-curve that has points labeled by a pair ,mn such that m is the index of the point, ()= mn f xb (thus, f is defined by mod 6 ()= mm fx b), and ()= m F xm . Since p is a covering map (by Example 4.12) and =pF f, F is a lifting of f with respect to p. liftings with respect to p to paths 0 F and 1 F, respectively, in Z , each starting at (0)))((0 1bfp . Since 5|>| Y, YxfN Y ),2)(( 0 , so p is a radius 2 local isomorphism. From Theorem 4.15, 0 F and 1 F must end at the same point. Indeed, this point must be 0, for the uniqueness of 1 F implies 1 F must be the cons- tant map 0. Since f is an antipodal map, we must have .1]/2[0,/2 = |)(/2)(|00 ZXYXntallforntFntF (4) Since 0=(0) 0 F, /2}/2,{/2)( 0YYXnnnF . Without loss of generality, /2.=/2)( 0YX nnF (5) Since F is continuous and 5> Y n, a simple induc- tion argument based on Equations (4) and (5) shows that )(>/2)( 00tFntFX for all ZX nt1]/2[0, . But since 0=)( 0X nF , this implies with Equation (4) that /2=/2)( 0YX nnF , which contradicts Equation (5). The assertion follows from the contradiction. 5. Antipodes Mapped Together A classical result of topology is that if f is a conti- nuous map from the d-dimensional unit sphere d S to Euclidean d-space d R, then there is a pair of antipodes d Sxx , such that )(=)( xfxf [17]. For 1=d, the following is a digital analog. Theorem 5.1 Let S be a digital simple closed l c-curve with 1 0= }{=n ii xS , where the points of S are circularly ordered. Suppose S is symmetric with respect to the origin. Suppose ZSf: is a ),( 1 ccl- continuous function. Then there is a pair of antipodes Sxx , such that 1|)()(| xfxf . Proof: By Lemma 4.4, n is even. Consider the function ZngZ 1][0,: defined by()=( ) i gif x (/2)mod () in n fx . By Lemma 4.5, we are done if, for some i, 0=)(ig . Therefore, we assume for all i that 0.)( ig (6) Clearly, for all i, ).(=]mod/2)[( ignnig (7) The continuity of f implies that 2.|1)()(| igig (8) It follows from Equation (7) that g takes both posi- tive and negative values, so from inequality (6), there is an index j such that )( jg and 1)( jg have oppo- site sign; without loss of generality, 0>)(jg and 0<1)( jg . From inequality (8), it follows that L. BOXER Copyright © 2010 SciRes. AM 385 Figure 7. S and : f SZ. Each number in the grid labels a point of S, showing the image of the grid point under f . Note for 0= (1,2)s, 00 |()( )|=1fsf s , but there is no s S for which ()= () f sfs. 1=)( jg , and the assertion follows. Theorem 5.1 parallels, in a sense, a result of [2]: In the Euclidean line, a continuous function mapping an interval to itself has a fixed point; in the digital world, a ),( 11cc - continuous function ZZbabaf ],[],[: has a “near- fixed” point, i.e. , a point x such that 1|)(| xfx . That we cannot, in general, conclude the existence of antipodes mapped to the same point in Theorem 5.1, is illustrated in the following example (note the simple closed curve has more than 4 points). Let=S {(,)|||||=3} xy xy. Then S is a simple closed 2 c- curve in 2 Z . The function ZSf : given by 3,=(0,3)=1,2)(=2,1)(=3,0)( ffff 2,=(1,2)=1)2,( ff 1,=(2,1)=2)1,( ff 0,=(3,0)=1)(2,=2)(1,=3)(0, ffff is a ),( 12cc -continuous function such that ()( ) f xfx 0 for each Sx. See Figure 7. 6. Further Remarks In this paper, we have obtained several analogs of classical theorems of Euclidean topology concerning maps on digital simple closed curves. We have shown that digital simple closed curves of more than 4 points are not contractible; that a continuous antipodal map from a digital simple closed curve to itself is not nullhomotopic; and that a continuous map from a digital simple closed curve to the digital line must map a pair of antipodes within 1 of each other. Except as indicated concerning whether or not a digital model of a sphere is contractible, it is not known at the current writing whether these results extend to higher dimensional digital models of Euclidean spheres. We thank the anonymous referees for their helpful suggestions. 7. References [1] A. Rosenfeld, “Digital Topology,” American Mathe- matical Monthly, Vol. 86, 1979, pp. 76-87. [2] A. Rosenfeld, “Continuous Functions on Digital Pic- tures,” Pattern Recognition Letters, Vol. 4, No. 3, 1986, pp. 177-184. [3] A. Rosenfeld, “Directions in Digital Topology,” 11th Summer Conference on General Topology and Applica- tions, 1995. http://atlas-conferences.com/cgi-bin/abstract/ caaf-71 [4] Q. F. Stout, “Topological Matching,” Proceedings 15th Annual Symposium on Theory of Computing, Boston, 1983, pp. 24-31. [5] T. Y. Kong, “A Digital Fundamental Group,” Computers and Graphics, Vol. 13, No. 1, 1989, pp. 159-166. [6] T. Y. Kong, A. W. Roscoe and A. Rosenfeld, “Concepts of Digital Topology,” Topology and Its Applications, Vol. 46, No. 3, 1992, pp. 219-262. [7] L. Boxer, “Digitally Continuous Functions,” Pattern Recognition Letters, Vol. 15, No. 8, 1994, pp. 833-839. [8] L. Boxer, “A Classical Construction for the Digital Fundamental Group,” Journal of Mathematical Imaging and Vision, Vol. 10, No. 1, 1999, pp. 51-62. [9] T. Y. Kong and A. Rosenfeld, “Topological Algorithms for Digital Image Processing,” Elsevier, New York, 1996. [10] L. Boxer, “Homotopy Properties of Sphere-Like Digital Images,” Journal of Mathematical Imaging and Vision, Vol. 24, No. 2, 2006, pp. 167-175. [11] G. T. Herman, “Oriented Surfaces in Digital Spaces,” CVGIP: Graphical Models and Image Processing, Vol. 55, No. 1, 1993, pp. 381-396. [12] L. Chen, “Gradually Varied Surfaces and Its Optimal Uniform Approximation,” SPIE Proceedings, Bellingham, Vol. 2182 1994, pp. 300-307. [13] L. Chen, “Discrete Surfaces and Manifolds,” Scientific Practical Computing, Rockville, 2004. [14] L. Boxer, “Digital Products, Wedges, and Covering Spaces,” Journal of Mathematical Imaging and Vision, Vol. 25, 2006, pp. 159-171. [15] U. Eckhardt and L. Latecki, “Digital Topology,” In: L. BOXER Copyright © 2010 SciRes. AM 386 Current Topics in Pattern Recognition Research, Research Trends, Council of Scientific Information, 1994. http://cosmic.rrz.uni-hamburg.de/webcat/mathematik/eck hardt/eck00001/eck00001.pdf [16] R. O. Duda, P. E. Hart and J. H. Munson, “Graphical Data Processing Research Study and Experimental Investigation,” Descriptive Note: Quarterly Report No. 7, March 1967, pp. 28-30. [17] E. Khalimsky, “Motion, Deformation, and Homotopy in Finite Spaces,” Proceedings IEEE International Confer- ence on Systems, Man, and Cybernetics, Boston, 1987, pp. 227-234. [18] L. Boxer, “Properties of Digital Homotopy,” Journal of Mathematical Imaging and Vision, Vol. 22, No. 1, 2005, pp. 19-26. [19] J. Dugundji, “Topology,” Allyn and Bacon, Inc., Boston, 1966. [20] S. E. Han, “Non-Product Property of the Digital Funda- mental Group,” Information Sciences, Vol. 171, No. 1-3, 2005, pp. 73-91. [21] S. E. Han, “Digital Coverings and Their Applications,” Journal of Applied Mathematics and Computing, Vol. 18, No. 1-2, 2005, pp. 487-495. |