48 CHARACTERIZATION OF CIRCUITS IN GRID OBTAINED BY REGULAR AND SEMI-REGULAR TESSELLATIONS INFORMATICA 4/89 JoviSa 2uni6, Novi Sad Faculty of Engineering Keywords: algorithm, circuit, tessellation Dr Ivan Stojmenovic, Institute of Mathematics, Novi Sad ABSTRACT: In this paper circuits in grids which are obtained by using plane tessellations are observed. Isomorphism and congruence of circuits in these grids is defined in natural way. Conection between these relations is discussed. 1. INTRODUCTION A tesselation of plane is a covering of the plane by using polygons. It is known that there are exactly eleven ways to cover plane by using regular polygons. Three of these are regular tessellations, where each vertex is surrounded by identical regular polygons (see fig.1). The other eight are semi-regular tessellations, in which each vertex is surrounded by an identical cycle of regular polygons (see fig.2). C«.a) (1.4) (.,,4) Figure 1. The three regular tesselations (3,3,3.4.4) (3.3,4,3,4) (3.3.3,3.6) (3,4,6.4) (3. 12.12) (4. 6,12) (4,8,8) (3,6,3,6) Figure 2. The eight semi-regular tesselations In this way eleven infinite periodic grids are obtained. (This grids are plane representation of infinite plane graphs.). Let G be one of obtained grids. A circuit of the lenght m in a grid G is a oriented closed path without repeated vertices, containg m edges. A circuit C in the grid G determines a simple polygon which consists of the edges of C, We will say that a circuit C] is congruent to a circuit C2 iff polygons determined by circuits C^ and Cg are congruent polygons. Also, in natural way we define an isomorphism of circuits in the grid G which is obtained by regular and semi-regular tessellations. Let C1 and C2 be the circuits in the grid G. Then: the circuits Ci and C2 are isomorphic circuits iff there exists a congruence transformation T such that: 1) T maps the grid G into itself and 2) T maps a polygon determined by the circuit Ci into polygon determined by circuit C2. Also we say that simple polygons A and B in the grid G are isomorphic polygons iff circuits determined by A and B are isomorphic circuits. 2, WORD REPRESENTATION OF CIRCUITS Let G be one of grids obtained by using tessellations. Grid G is periodic. Let us determine period of grid G. If n is the number of edges in period of G then the number of oriented edges is 2n and we shall denote these oriented edges (vectors) by v(0),v(1),...,v(2n-1).ln'this way for any oriented edge of the grid G there is corres-x •ponding-uniquely determined vectcrr"from the set v={v(0), v(1),...,v(2n-1)}. Let A. and B be points in the grid G, and P oriented path of lenght t, from A to B, If path P consists of oriented edges v(ii),v(i2),..,,v(it) respectively, then the word f(P)=iii2.,..it which corresponds to path P is uniquely determined. Speclaly, for i=1 f(v(i))=i. Let A^ be the set of all words of lenght k over the alphabet A= ={0,1.....2n-1) and A'=U Ak k>0. Then denote by A" the set of all words which corresponds to oriented pats in the grid G. That means: aGA'*:=> exists path P such that f(P)=a. If the word a-ii1o...1t is from A", then a determines the path v(i])..,v(it) such that f(P)=a. The circuit C of lenght n determines 2n closed oriented paths, depending on the choice of the initial vertex and the orientation of the circuit. A function f maps these 2n oriented paths into 2n words of the set A". Let us denote the set of these 2n words by Q(C) (for circuit C). Let T be isometry which maps grid G into itself. Let T(v(i))=v(i") i=0,1,2, .,.,2n-1 then (0',1*.....(2n-1)") is permutation of (0,1, ...,2n-1). Transformation T maps path P=v(ij)v{i2)••• v(it) into path T(P) such that T(P)=T(v(i1)v(i2)...v(it)) =T(v(i1))T(v(i2))...T(v(it))=v(if)v(i2)...v(1t} or f(T(P))=ifi?..-it- Let A1" Be the set of all words which correspond to circuits in the grid G. Also every word a from A"1 (a=i] ...it) determines circuit C=v(ii)v(i2).. .v(i't) (which determines simple polygon with edges of C). Let a and b be words from A'" , We say that a and b are in the relation a iff circuits, which are determined by words a and b, are isomorphic circuits. LEMMA 1: Relation a is equivalence relation. PROOF: The set r of all congruence transformations which map grid G into itself is a group. Specialy: If T=I (identical mapping) then for a,bGQ(C)*> aab. In the set of vectors {v(0),v(1),...,v(2n-1)} we define relation p by: v(i) v(j) exists isometry T which maps the grid G into itself such that T(v(i)) = T(v(J>) LEMMA 2: Relation p is a relation of equivalence. PROOF: Directly from definition. 49 Also, we say that: ipj iff v(i)pv(j), + If P is a path from point A to point B then vector AB is equal to the vector sum of oriented edges which the path P contains. LEMMA 3: :Word a=iii?...it from A" is from A" v(i1)v(i2)...v(it) is circuit) iff 1) v(it)=0 (vector summ) and 2) v(i j)+v(i j+1 )-t (or circuit) iff 1) v{i1)+v(12)+.. v(iJ-+k)/i0 for k Is from A" and ii pj'i then there exists a word b=j-jJ2-..jt suc^ ^at That means: the number of initial vectors can be equals to the number of equivalence classes with respect to relation p. In this way can be reduce the computation time. 5) Initial vectors-corresponding characters denoted by Iv(1)ilv(2),... ,Iv(I). 6) Number of transformations (of t). 7) One isometry of first class which maps grid into itself. 8) One isometry of second class which maps grid into itself. 9) For every vector v(i) its opposite vector v(j). (,(i)=-v(j)). Note: for grid 3 .6 isometry of first class no exists so 7 is identical mapping. Let a=iii2...it tie word from A", and let a(j) denoted the word 1jij+l...it '-0-t. If CONDITION-G is not satisfied for any j(1.Sj't} a representing a circuit iff i -ji2 ...it is addable. Also it is obvious that a=iii2...it denotes a circuit iff a(j) satisfied CONDITION-G only for j=l. All words that are a-equivalent to a word a representing a circuit we can obtain using 6,7,8,9 (see input data). We consider only the equivalent words begining by one of initial vectors (input data-5) and sort them in lexicographic order. We choose the first word a' as a representative of this class. Hence, if the word a is equal to a', then word a represents a circuits of lenght t and print it. Our algorithm can be conveniently explained using two phases: extend and reduce. These phases correspond to the addable and nonaddable cases respectively. READ (t) FOR k=1 to I DO BEGIN i1=Iv(k); m:=1 REPEAT IF i1i2-•.im is addable THEN extend ELSE IF ili2• • •''111 is representative of a nonisomorphic circuits THEM print i]i2...im reduce UNTIL m=l END where extends BEGIN m:=nH-1; im:=c(fm_t • 1) END reduces WHILE im=c(im_iC) and ml2 DO m:=m-l IF mjil THEN BEGIN t:=0 REPEAT t:=t+1 UNTIL infcOm-l.t) im:=c(1m-1«t+l) END Data obtained by proposed algorithm will be given in next section, k(t) denoted the number of nortisomorphic circuits lenght of t. Grids which is obtained by tessellations e3^1*^6 are not specialy treated, but they have been observed in the papers: |i|,|2|,|3|. The algorithm presented here could be also directly applied to these a rids. 4. CONNECTION BETWEEN ISOMORPHISM AND CONGRUENCE OF CIRCUITS It is clear that if C] and C2 are isomorphic circuits then Cj and C2 are congruent circuits. In this section we will-show that for grfBs obtained by tessellations 33.42, 32.4.3.4, 3.4.6.4, 3.6.3.6, 3.122, 4.6.12, 4.82 (all semi-regular except 3^6) is satisfied: if circuits C^ and C2 are congruent circuits then they are isomorphic circuits. For grids obtained by regular tessellations previous statament follows obviously because of that they are not specialy treated. In proofs of following lemmas we will use: LEMMA 6: Let M=MiM2...Mt and N=NiN2...Nt be congruent polygons such that Mii=Nii,Mi2=Ni2,M|2SNij(for some integres i1;i2>i3 from (1,2,...,t), then: if points M^i.M^i and Mis are not colinear then M-j^Ni for all i£{1,2,...,t}. We shall denote by }(i,j) the angle between vecto.rs v(i) and v(j), By r(M) will denoted the word ml ,2...v«i determined by a simpl polygon M=MjM2...Mt such that mi = -f(Mitfi+i). LEMMA 7: Let G be the grid obtained by tessellation 3\42, then: if M and N are congruent polygons in grid G then r(M)ar(N). PROOF: Equivalence classes with respect to relation p are: I={0,5} 11=11,4,9,6} III={2,3,7,8} (see fig.3) Let M=MiM2.,.Mt and N=N]N2...Nt are congruent polygons in the grid G_and r(M)=m]m2..,mt and r(N)=nin2.. .nt. nmm V/AM\/A . VECTORS: 5 6 7 8 9.are opposite for: 0 12 3 4 \lV/A WJmL k(t): • ? 2 2 4 6 ■V/M//,\n S-initial vertex mimxmm wmff/7/m/m 8 9 10 11 17 32 90 204 f(P) = 0231 208935759020235 7575444084 ng, i. 1-case:ni],njGI then mjm2...mja0m2...m£ and n^...n^-ctOn^ ,.,n{ (words Om^.-.m^ and Ong.-.n^ exist because m^ and ni are from same equivalence class) if m^ng then by Lemma 6 m{=n{ for i=3,,..,t if m^ng then we apply reflection in 50 a line determined by vector v(0) which maps grid G into itself. The image of Om^.-.nit is Om§...m^. ,0 1 2 3 4 5 6 7 8 9, case: m^ nta11n' 0687951324 emma since M°.ra2)=H°>n2) we have mrni' m^. ..nuaOnJ-mtaOnjim!}.. .m't, n^...n^aOn^...n£ that means (by Le 6J n3=ni3.....nt=mt or m1m2' • •ratcin1n2-• "nt- 2-case: mjniG||then m^.. .m^alm^. • and n^.. .ntm2=n2 If m2=n2=1 then we continue until but then using Lemma 6 mi=n{ or mim2. m^almj...mj=1n^...n£anjn2-..n^. m^a2m2..and n^n2* 3-case: m-|.n'jGIII then m^ nta2np... nl K2,m|)=H2,n2) if m2=n2 then clearly for i=3,...,t and m^mg... mtanin2-..nt if m^n? then, let be for example, ni2=3 and n2=4, now Jt3.m, and ^ that means 2m2-..mi=236 and 2n2-..n{=243 but 2 36a 2 43 4-case: m1G|n^Gj |then mim2-..mtot°n,2• • *mt and n^-'-ntaOnJ.-.ni )(0.m2)"iM' ."¿J""anc' n2=5 continuing we have Om^... m£=0 154 and 1ri2.. .n£=1 5 4 0, but-0 1 5 4a 1 5 40 5-case: ni)G|, n-|G | j | then rnjn^.. .mta0m2.. and n^... nta2n2...ni K0,m2)=n?=0 and m?G{8,2} if mj=8 applying o0 we have mim?.. .mtaO 2m3.. .mi nin?.. .nj-a2 0 n?.. .ni continuing we get 0 21113.. .m£=0 20 2 ... and 2 0 . .n£= =20 20 ... but this words are not from A"1. 6-case: miG|[ , n 1611j then mini2-• .mtalm^.. .mi and n^... nta2n2.-.f>t We are interested in the case when m^ and n^ do not satisfy any of previous observed cases. If for some i one of them is satisfied then we observe polygons MiM2-..n£)}. Since M' and N* are congruent, there exist isometry S which maps plane into itself such that S(M')=S(ABM3...M£)=S{A)S(8)^;i3-).. ■S(M£)=BAN3...N£=N*. But then S is either * - 1) reflection in line s which is symmetry axes of segment |AB|. or 2) half turn with centre in middle of segment |AB|. If S is reflection then images of edges denoted by broken line ( —) do not belong to grid G; therefore ed-Iges of polygon BAN3...N* can be some of edges denoted with ----. Since polygonis conected, we conclude n£7.But for ni7 there are thirteen different a-equivalence classes and representatives of this classes are not congruent polygons so statement follows. In the case when S is half turn, proof is analogous. For grid G obtained by tessellation S1*^ (see fig.5) words which correspond to congruence polygons do not have to be a-equivalent. For example: for congruent triangles A and B (as it is shown in fig. 5) r(A)ar(B) but there is no isometry which 1) maps grid G into itself, 2) maps A into B. 9 3 " 1 10 ft % VECTORS:15 16 for: 0 1 28 29 are opposite 13 14 t: 3 4 5 6 7 8 k(t): 2 2 2 5 5 13 initial vertex f(P) = 23 10 26 22 1 2 22 15 25 9 4 5 26 3 4 506 27 1106 rig. S. The proofs of following lemmas are omited, since they are analogous to proofs of Theorem 1 and Theorem 2. LEMMA 9: Let G be the grid obtained by tesselations 3.4.6.4, Then: if M and N jre congruent polygons in grid G then r(M)ar(N). PROOF: Equivalence classes with respect to relation p are: l={0,1,2,3,4,5,12,13,14,15,16,17} |={6,7,8,9,10,11,18,19,20,21,22,23} VECTORS:12 13 ... 22 23 are opposite for: 0 1 ...-10 11 t: 3 4 5 6 7 8 9 a o k(t): J oO 44 33 4 initial vertex f(P) = 1 9 17 16 10 17 16 10 17 23 14 13 7 3 ' 10 17 18 7 3 4 5 22 15 14 13 6 5 0 1 • u. LEMMA 10: Let G be the grid obtained by tesselation 3.6.3.6. Then: if M and N are polygons in grid G then r(M)ar(N). PROOF: There exist only one equivalence classes with respect to relation p. 1=^(6,112,3,4,5,6,7,8,9,10,11} 3.2. •Q . \VECTORS:6 7 8 9 10 11 are opposite for: 0 1 2 3 4 5 JL, 3 4 5 6 7 8 9 M 1 2 1 2 4 initial vertex 51 f(P) = 10 1 2 11 2 0 1 2 3 4 7 6 11 10 6 3 4 79879045098 LEMMA 11: Let G be the grid obtained by tessellations 3.122. Then if M and N are congruent polygons in grid G then r(M)ar(N). PROOF: Equivalence classes with respect to relation p are: l={0,2,4,5,8,10,12,13,14,15,16,17} '={1,3,5,7,9,11}. c initial vertex. VECTORS: 17 7 16 9 12 11 14 13 15 are opposite for : 0 1 2 3 4 5 6 8 10 t: 3 12 13 14 15 15 17 18 k(t): 1113 3 3 11 f(P) =1 14 11 0 1 2 3 4 5 15 16 7 8 4 5 15 16 7 8 9 16 14 11 0 rig. o. LEMMA 12-: Let G be the grid obtained by tessellation 4.6.12 then: if M and N are congruent polygons in grid G then r(M)ar(N): PROOF: Equivalence classes with respect to rellation p are: I=t0,2,4,6,8,10,18,20,22,24,26,28} ll={ 1,3,5,7,9,11,19,21,23,25,27,29} |={12,13,14,15.16,17,30,31,32,33,34,35} O initial vertex f(P) = 29 28 27 26 25 31 19 18 29 35 6 31 19 18 29 35 23 22 15 9 10 35 23 16 0 1 13 24 23 16 VECTORS: 18 19 ... 34 35 are'opposite for: 0 1 ... 16 17 t: 4 5 6 7 8 9 10 11 12 13 14 15 16 k(t): 1010101030209 Fig. 9. LEMMA 13. Let G be the grid obtained by tessellation 4.82 then: if M, N are congruent polygons in grid G then r(M)ar(N). PROOF: Equivalence classes with respect relation p are: |={0,2,4,6} ; ¡¡={1,3,5,7,9,10,11} VECTORS: 4 11 6 8 9 10 are opposite for: 0 12 3 5 7 3 4 5 6 7 8 9 10 11 12 13 14 0 1 0 0.0 1 0 1 0 2 0 4 initial vertex f(P) = 28 1 25 10 284967984967 0 3 6 7 0 1 rig. iu. Let grid G be obtained by one of semi-regular tessellations 33.42, 32.4.3.4, 3.4.6.4, 3.6.3.6, 3.122, 4.6.12, 4.82 then from lemmas 6-13 follows: THEOREM 1: Circuits C, and C2 in grid G are isomorphic circuits iff they are congruent circuits. REFERENCES |1| DoroslovaCki R., StojmenoviC I., To5ii R., "Generating and counting triangular systems", BIT, 1987, 27, I, 1987, 18-24. |2| Robert A. Metier, "Tessellation graph characterization using Rosettas", Pattern Recogrition Letters 4 (1986) 79-85 |3| StojmenoviC I., ToSii R., DoroslovaCki R., "An algorithm for generating and counting hexagonal systems", Proc. of the 6-th Yugoslav Seminar on Graph -Theory and Lectures for Research Seminar, Dufej-ovnik 1986 , Institut of Mathematics, Univ. of Novi Sad> 1986, 189-198. |4| TepavCeviC A., StojmenoviC I., "Counting Nonisomorp-hic pats in triangle-hexagonal grids", IX medjunaro-dni simpozij "Kompjuter na sveuCiliStu", 1987, IISOI 1-4. |5| ToSiC R., DoroslovaCki R., "Characterization of hexa gonal systems", Rev. of Res., Fac. of Sci. Math, Ser Novi Sad 14, 2, 1984, 201-208. |6| 2uniC 0., StojmenoviC I., "Counting nonisomorpphic circuits 1n grids obtained by regular and semi-regular tessellations", XI medjunarodni simpozijum "Komp juter na sveuCiliStu", 1989, to appear.