General neighborhood sequences in Zn

Gene al neighbo hood sequences in Zn And ´as Hajdu a,1Lajos Hajdu b,2Robe Tijdeman c,3 aFacul y o In o ma ics, Uni e si y o Deb ecen, H-4010 Deb ecen, P.O.Box 12. bNumbe Theo y Resea ch G oup o he Hunga ian Academy o Sciences, and Ins i u e o Ma hema ics, Uni e si y o Deb ecen, H-4010 Deb ecen, P.O.Box 12. cMa hema ical Ins i u e, Leiden Uni e si y, NL-2300 RA Leiden, Pos bus 9512. Abs ac Neighbo hoods and neighbo hood sequences play impo an oles in se e al b anches o pa e n analysis. In ea lie pape s in Znonly ce ain special (e.g. pe iodic o oc ag- onal) sequences we e in es iga ed. In his pape we s udy neighbo hood sequences which a e ei he ul ima ely pe iodic o allow a e e y neighbo hood o do no hing a no cos . We gi e ini e p ocedu es and desc ip i e heo e ical c i e ia o ce ain impo an (e.g. me ical) p ope ies o he sequences. Ou esul s a e alid o se - e al ypes o classical neighbo hood sequences and o gene a ed dis ance unc ions (e.g. oc agonal and cham e dis ances) which a e widely applied in digi al image p ocessing. We conclude he pape by showing how ou esul s con ibu e o he heo y o dis ance ans o ma ions. Key wo ds: Combina o ial algo i hms, Pa h and ci cui p oblems, Geome ic algo i hms, languages and sys ems, Image p ocessing and compu e ision PACS: 68U10, 41A50 1 In oduc ion In [30] Yamashi a and Iba aki in oduced he concep o gene al pe iodic neighbo hood sequences in Zn. They in es iga ed when such sequences gen- 1Resea ch suppo ed in pa by he OTKA g an F043090, and by he IKTA4 g an 6/2001. 2Resea ch suppo ed in pa by he Ne he lands O ganiza ion o Scien i ic Re- sea ch (NWO), he J´anos Bolyai Resea ch Fellowship o he Hunga ian Academy o Sciences and by he OTKA g an s T042985, F034981, F043090, and T048791. 3Resea ch suppo ed in pa by he Ne he lands O ganiza ion o Scien i ic Re- sea ch (NWO). e a e me ics, and he ela ion o hese me ics and he Euclidean one. Thei main esul s a e he exhibi ion o ce ain p ocedu es, which decide abou he me ici y and ela ed p ope ies. Das e al. [6] specialized his heo y o he so-called oc agonal sequences, based on he adi ional neighbo ing ela ions o digi al image p ocessing. Fo a ious esul s in his di ec ion we e e o [1,3,5,7–10,23,27], and he e e ences gi en he e. Recen ly, Fazekas e al. [12] d opped he pe iodici y equi emen om he model o [6] by in oducing gene al (no necessa ily pe iodic) oc agonal neighbo hood sequences. This ex ension is impo an no only om a heo e ical bu also om a p ac ical poin o iew, since e.g. he Euclidean me ic can be app oxima ed mo e p ecisely by gene al oc agonal neighbo hood sequences han by pe iodic ones, see [18]. Fu he esul s abou gene al oc agonal neighbo hood sequences can be ound e.g. in [16,17,24–26]. The pu pose o his pape is wo old. On he one hand, we ex end he heo y o gene al (no necessa ily oc agonal) neighbo hood sequences om he pe i- odic case (in es iga ed in [30]) o he case o neighbo hood sequences which a e de ined o e an a bi a y ini e alphabe , and a e ei he ul ima ely pe- iodic o allow a e e y neighbo hood o do no hing a no cos . The se o ul ima ely pe iodic neighbo hood sequences has he ad an age o be a he la ge, al hough such a sequence is de e mined by only ini ely many da a. We gi e p ocedu es and p o ide heo ems o ce ain impo an c i e ia (e.g. me ici y). These heo e ical esul s gi e a good insigh in o he beha io o such sequences. We ha e no compu ed he complexi y o ou p ocedu es, i is le as an open issue (see Sec ion 9). The s uc u e o he pape is as ollows. In Sec ion 2 we gi e he basic no- a ion and de ini ions. Some p elimina y esul s a e p esen ed in Sec ion 3. In Sec ion 4 we show how ce ain sequences can be simpli ied keeping hei me ical p ope ies. We cha ac e ize he neighbo hood sequences o which Zn is connec ed in Sec ion 5. In Sec ion 6 he me ical beha iou o neighbo hood sequences is in es iga ed. Sec ion 7 con ains ou esul s on app oxima ing he Euclidean me ic wi h dis ance unc ions based on neighbo hood sequences. In Sec ion 8 we show how ou model can be used e.g. in he heo y o dis ance ans o ma ions. Finally, we discuss on cu en ela ing esea ch esul s, and conclude in Sec ion 9. 2 Basic concep s and no a ion Le R,Q,Z,Ndeno e he se s o eal numbe s, a ional numbe s, in ege s and posi i e in ege s, and w i e R≥0,Q≥0,Z≥0 o he subse s consis ing o he non-nega i e elemen s o hese se s, espec i ely. We ix a posi i e in ege 2 n o he whole pape , and w i e O o he o igin o Rn. Le H={hi∈Zni= 1,...,m}and X⊆R. Then he cone gene a ed by H o e Xis de ined as H<(X) = (m X i=1 λihiλi∈X, i = 1,...,m). A neighbo hood is a pai (P, w), whe e he poin se P⊆Znis ini e, and w:P→R≥0is a so-called weigh unc ion on P. Fo p∈P,w(p) is he weigh o pwi h espec o w. The neighbo hood (P, w) is called symme ic, i o any p∈P,−p∈Pand w(p) = w(−p). Le Λ be a ini e se o neighbo hoods. An n-dimensional (sho ly nD) neigh- bo hood sequence is de ined as a sequence N= (Ni)∞ i=1 o e Λ, ha is, Ni∈Λ o all i∈N. We call Λ he alphabe used o N. Le Sndeno e he se o all nD-neighbo hood sequences. I o some j∈N,Ni=Ni+j o all i∈N, hen Nis called pe iodic wi h pe iod j. In his case we use he b ie no a ion N=N1N2. . . Nj. I j= 1 hen Nis called a cons an neighbo hood sequence. Le N(k)deno e he neighbo hood sequence ob ained by omi ing he i s k elemen s o N∈Sn. The sequence N= (Ni)∞ i=1 is called ul ima ely pe iodic, i N(k)is pe iodic o some k∈N. I N(k)has pe iod leng h l−k, hen we w i e N=N1N2. . . NkNk+1 . . . Nl. Fo echnical easons i is use ul o a oid he degene a e case k= 0. Thus h oughou he pape we assume ha he pe iodic sequence N=N1N2. . . Nlis gi en by N=N1N2. . . NlN1N2. . . Nl. We use he ollowing no a ion o some special subse s o he se o nD- neighbo hood sequences Sn: Sp n={N∈SnNis pe iodic}, Su n={N∈SnNis ul ima ely pe iodic}, SO n={N= (Ni)∞ i=1 ∈Sn|Ni= (Pi, wi),O∈Pi, wi(O) = 0 o all i∈N}. The se SO nwill play a special and impo an ole h oughou he pape . Mo eo e , i is clea ha Sp n(Su n. We can measu e dis ance by he help o neighbo hood sequences in a na u al way (see e.g. [6,12,30]). Le qand be wo poin s in Zn, and N= (Ni)∞ i=1 ∈Sn, wi h Ni= (Pi, wi). The poin sequence s= [q0, q1,...,qm], whe e q=q0, =qm, and qi−qi−1∈Pi, is called an N-pa h be ween qand . De ine he ela ion ∼on he se A:= {(q1−q0,1),...,(qm−qm−1, m)}as (qi−qi−1, i)∼ (qj−qj−1, j) i and only i qi−qi−1=qj−qj−1and wi(qi−qi−1) = wj(qj−qj−1). Ob iously, ∼is an equi alence ela ion on A. Conside he pa i ion A= S i=1 Ai induced by ∼on Awi h he app op ia e ∈N. Then, as a sho hand, we w i e 3 s= −q= P i=1 λixi, whe e xiis he common i s en y o he pai s in Ai, and λi=|Ai|deno es he ca dinali y o Ai(i= 1,..., ). The leng h o sis de ined as ℓ(s;N) = m P i=1 wi(qi−qi−1) = P i=1 λiw(i)(xi), whe e w(i)deno es he common weigh o he i s en ies o he pai s in Ai. I Nis ixed, hen we sho ly w i e ℓ(s;N) = ℓ(s). The N-dis ance W(q, ;N) be ween qand is de ined as he leng h o a sho es N-pa h be ween hem, i such a pa h exis s. Pu W(q, q;N) = 0 o q∈Zn(emp y pa h). I he e is no pa h be ween qand , we se W(q, ;N) = ∞. We w i e W(N) o he dis ance unc ion i sel de ined by Non Zn, and also use he b ie no a ion W(q, ), i Nis ixed. Mo eo e , we pu W(q;N) = W(q) = W(O, q). I o all q, , s ∈Znwe ha e W(q, ;N)<∞(Wis ini e) W(q, ;N)≥0, W(q, ;N) = 0 i q= (Wis posi i e de ini e) W(q, ;N) = W( , q;N) (Wis symme ic) W(q, ;N) + W( , s;N)≥W(q, s;N) (Wsa is ies iangle inequali y) hen we call W(N) a me ic, and use he no a ion d(q, ;N) = W(q, ;N), o sho ly d(q, ) = W(q, ) and d(N) = W(N). Mo eo e , we w i e d(q;N) = d(q) o d(O, q). Fo x∈Rn, le ||x||1:= n P i=1 |xi|and ||x||2:= sn P i=1 x2 ideno e he diamond no m and Euclidean no m, espec i ely. We say ha Znis N-connec ed, i o any wo poin s o Zn he e exis s an N-pa h be ween hem. I Nis ixed, we will sho ly say ha Znis connec ed. No e ha Znis N-connec ed i and only i W(q) is ini e o all q∈Zn. A se T⊆Znis said o allow a ini e co e ing o Zn, i Zncan be co e ed by he union o ini ely many ansla es o T. By a la ice we mean a subg oup o Zn. A la ice is called ull i i has ank n. We in oduce a pa ial o de ing ela ion on Sn, which will be impo an in ou in es iga ions. We no e ha o ce ain special neighbo hood sequences such a ela ion was used by Das e al. [6], Fazekas [11] and by Fazekas e al. [12]. Le N, N′∈Sn. We de ine he ela ion ⊒∗on Snby N⊒∗N′i and only i W(q, ;N)≤W(q, ;N′) o all q, ∈Zn, and we can also say ha Nis as e han N′. 4 3 P elimina y esul s F om he ollowing p oposi ion we can see ha he neighbo hood model is sui able o measu ing dis ances, since i assu es he exis ence o a sho es pa h, i Znis connec ed. P oposi ion 1 Le N= (Ni)∞ i=1 ∈Snwi h Ni= (Pi, wi). Then o all q, ∈ Zn,W(q, ;N)exis s. PROOF. I he e is no pa h be ween qand hen by de ini ion W(q, ;N) = ∞. O he wise, le sbe an a bi a y bu ixed pa h om q o o leng h ℓ(s), ha ing he sho o m s= P i=1 λixi. Suppose ha s′= ′ P j=1 λ′ jx′ jis a pa h om q o o leng h ℓ(s′) such ha ℓ(s′)< ℓ(s). Then o any j∈ {1,..., ′}, o he coe icien s λ′ jo hose x′ jin s′ o which w(j)(x′ j)>0, we ha e λ′ j≤ ℓ(s)/w(j)(x′ j). Thus, as he e a e only ini ely many neighbo hoods, and e e y neighbo hood con ains only ini ely many poin s, he e a e only ini ely many possibili ies o he leng hs o such pa hs s′ om q o . Hence he s a emen ollows. 2 The ollowing examples explain why he es ic ions |Pi|<∞ o all i∈N, and |Λ|<∞a e necessa y o ha e P oposi ion 1. In ou i s example we show why we a oid in ini e neighbo hoods. Example 2 Le N=N1∈Sp 1be a cons an neighbo hood sequence, wi h N1= (Z, w1). Fo e e y i∈Z, le w1(i) = |1/i|i i6= 0, and le w1(0) = 0. In his case W(0,1; N)does no exis , since he e is no sho es pa h be ween 0 and 1. Fo example, he leng h o he pa h 0,−i, 1is 1 i+1 i+1 o e e y i∈N. Ou nex example shows why i would be inapp op ia e o de ine neighbo hood sequences o e an in ini e alphabe . Example 3 Le N= (Ni)∞ i=1 ∈S1, wi h Ni= (Pi, wi), whe e Pi={±i, 0}, wi(±i) = |1/i|and wi(0) = 0 o e e y i∈N. Now he alphabe o neighbo - hoods Λis no ini e, and simila ly o he p e ious example, W(0,1; N)does no exis , because he e is no sho es pa h be ween 0and 1. 4 Equi alen neighbo hood sequences In his sec ion we in es iga e unde wha ci cums ances he s uc u e o a neighbo hood sequence can be simpli ied wi hou a ec ing i s dis ance mea- 5 su emen . Rema k 4 No e ha ou model allows posi i e weigh o keeping place du ing he mo emen . Using sequences om SO nmakes i possible o keep place and a oid in olun a y mo emen s o undesi ed places. In pa icula , we ha e he ollowing s a emen : P oposi ion 5 Fo any N∈SO n he e exis s an M∈Su no he o m M= M1. . . MkMk+1, such ha he unc ions W(N)and W(M)a e iden ical on Zn. PROOF. The neighbo hood Mk+1 = (P′ k+1, w′ k+1) can be de ined as ollows. Le I={i|Ni= (Pi, wi) occu s in ini ely o en in N}. Pu P′ k+1 =S i∈I Pi, w′ k+1(p) = min i∈I{wi(p)|p∈Pi} o each p∈P′ k+1. Le he sequence o neigh- bo hoods M1,...,Mkbe he subsequence o Nconsis ing o he elemen s o N which occu only ini ely many imes and w i e M=M1. . . MkMk+1. Clea ly, by hese choices we ha e W(N) = W(M). 2 Yamashi a and Iba aki [30] showed ha i N∈Sp nand W(N) is a me ic, hen he e exis s a cons an neighbo hood sequence M∈Sp nsuch ha d(N) is iden ical wi h d(M). The ollowing example shows ha his esul canno be ex ended in his o m o he ul ima ely pe iodic case. Example 6 Le n= 1,N1= (P1, w1),N2= (P2, w2), wi h P1={0}, P2={±1},w1(0) = 1,w2(±1) = 1, and conside N=N1N2. I is ob i- ous, ha W(N)is a me ic, since W(0; N) = 0 (as always, by de ini ion) and W(x;N) = |x|+ 1 o any x∈Z {0}. Howe e , i can be easily seen ha N canno be eplaced by a cons an neighbo hood sequence. I u ns ou ha a a ian o he abo e esul is s ill alid o ul ima ely pe iodic sequences. P oposi ion 7 Le N=N1. . . NkNk+1 . . . Nl∈Su nwi h Ni= (Pi, wi) o i∈ {1,...,l}. Then he e exis s an M∈Su no he o m M=M1. . . MkMk+1 such ha W(N)and W(M)a e iden ical on Zn. PROOF. Le P= l−1 [ =k( X i=k bibi∈Pi, i =k,..., ),and 6 P′=   l X i=k+1 bibi∈Pi, i =k+ 1,...,l   . Conside he neighbo hood T= (P, wP), whe e o e e y x∈P wP(x) = min ( X i=k wi(bi)x= X i=k bi, =k,...,l−1, bi∈Pi, i =k, . . . ), and T′= (P′, wP′), whe e o e e y x∈P′ wP′(x) = min    l X i=k+1 wi(bi)x= l X i=k+1 bi, bi∈Pi, i =k+ 1,...,l   . The neighbo hood sequence M=N1. . . Nk−1TT′ob iously has he desi ed p ope y, and he p oo o he p oposi ion is comple e. 2 F om Example 6 we see ha i is no ue ha o e e y neighbo hood sequence we can ind a cons an one such ha hey induce he same me ic. Now we show ha , on he con a y, he elemen s o SO nha e his p ope y. Theo em 8 Suppose ha N∈SO ninduces a me ic on Zn. Then he e is a cons an neighbo hood sequence which induces he same me ic on Zn. PROOF. By P oposi ion 5 we may assume ha N=N1. . . NkNk+1 wi h Ni= (Pi, wi) o i∈ {1,...,k+ 1}. Le dbe he me ic induced by Non Zn, and le P=k+1 S i=1 Pi. Mo eo e , o e e y x∈Pse wP(x) = min {wi(x)x∈Pi, i = 1,...,k+ 1}, and pu T= (P, wP) and M=T. We claim ha d=W(M). By he de ini ion o Mi is clea ha Znis M-connec ed, and ha o e e y x∈Znwe ha e d(x)≥W(x;M). Take an a bi a y x∈Zn, and choose a sho es M-pa h [O=q0, q1,...,q =x] om O o x. Then using ha wP(y)≥d(y) o e e y y∈Pand ha dsa is ies he iangle inequali y, we ha e W(x;M) = X i=1 wP(qi−qi−1)≥ X i=1 d(qi−qi−1)≥d(x). Hence W(M) = don Zn.2 I is clea ha i in Theo em 8 he neighbo hoods in Na e gi en, hen he cons an neighbo hood sequence can be cons uc ed by a simple p ocedu e. 7 P oposi ion 9 Suppose ha N= (Ni)∞ i=1 ∈SO ninduces a me ic don Zn, and wi(x) = 1 o each x∈Pi {O}, o all i∈N. Then dis comple ely de e mined by he se {xd(x) = 1}. PROOF. Clea ly, d(x) = 0 i and only i x=O, and d(x) = 1 i and only i x∈P:= ∞ S i=1 Pi {O}. Since wP≡1 and dis comple ely de e mined by (P, wP), he s a emen ollows. 2 5 Connec edness o Zn In his sec ion we cha ac e ize he ul ima ely pe iodic neighbo hood sequences o which Znis connec ed. Fo his pu pose we need he ollowing lemma. Lemma 10 Le H={hi∈Zni= 1,...,m}. Then H<(Z≥0)allows a ini e co e ing o Zni and only i i is a ull la ice. PROOF. Clea ly, i H<(Z≥0) is a ull la ice, hen i allows a ini e co e ing o Zn. To p o e he o he di ec ion, assume ha H<(Z≥0) allows a ini e co- e ing o Zn. We no e ha i is well-known ha he se o in eg al poin s in he cone H<(Q≥0) ha e a (so-called Hilbe ’s) basis; see e.g. [15]. As H<(Q≥0) is a a ional cone, ei he i is con ained in a ( a ional) hal space o Qn, o H<(Q≥0) = Qnholds. Since H<(Z≥0) allows a ini e co e ing o Zn, he o me case can be excluded. In he la e case, le l∈ {1,...,m}be a bi a y. Then he e a e non-nega i e in ege s i, siwi h si6= 0 (i= 1,...,m), such ha −hl=m P i=1 i sihi. Hence −hl=   ( l+sl) m Y j=1 j6=l sj−1   hl+ m X i=1 i6=l     i m Y j=1 j6=i sj   hi, implying −hl∈H<(Z≥0). Hence H<(Z≥0) is a la ice. The ac ha his la ice is ull ollows om H<(Q≥0) = Qn, and he p oo is comple e. 2 Theo em 11 Le N=N1. . . NkNk+1 . . . Nl∈Su nwi h Ni= (Pi, wi) o i∈ {1,...,l}, and pu Q = l−1 [ =k( X i=1 bibi∈Pi, i = 1,..., ), 8 Q∞=   l X i=k+1 bibi∈Pi, i =k+ 1,...,l   . Then Znis N-connec ed i and only i Q< ∞(Z≥0)is a ull la ice in Rnand Q ep esen s all he cose s o he la ice Q< ∞(Z≥0)in Zn. Mo eo e , he connec edness o Zncan be checked by a ini e p ocedu e. PROOF. The su iciency o he condi ion is clea . To p o e he necessi y, assume ha Znis N-connec ed. Obse e ha hen Q< ∞(Z≥0) allows a ini e co e ing o Zn. By Lemma 10 his is equi alen o saying ha Q< ∞(Z≥0) is a ull la ice. Mo eo e , o he connec edness o Zn, we also need ha all he cose s in Zno he la ice Q< ∞(Z≥0) a e ep esen ed by Q . Clea ly, i is a ini e p ocedu e o check whe he Q< ∞(Z≥0) is a ull la ice o no . Ac ually, i is su icien o check whe he Q∞con ains nlinea ly independen ec o s o e Q, and ha −h∈Q< ∞(Z≥0) o e e y h∈Q∞. The o me p oblem is easy. The la e one leads o an in ege p og amming p oblem o he o m Ax =b, x ≥0 in x∈Zm,(1) whe e b=−h∈Zn,m=|Q∞|, and he column ec o s o he n×m ype ma ix Aa e jus he elemen s o Q∞. The algo i hmic solu ion o (1) is well-known, e en i an objec i e unc ion m P i=1 cixi,x= (x1,...,xm), ci∈R (i= 1,...,m) should also be maximized (see e.g. [13]). I Q< ∞(Z≥0) is a ull la ice, hen we need only a ini e amoun o compu a ion o e i y he second pa o he condi ion. I su ices o enume a e Q and o check whe he all he cose s in Zno he la ice Q< ∞(Z≥0) a e ep esen ed o no . Thus we ha e a ini e p ocedu e o check he connec edness o Zn, and he heo em ollows. 2 Co olla y 12 I Nis a cons an neighbo hood sequence hen Znis N-connec- ed i and only i Q< ∞(Z≥0) = Zn. Co olla y 13 Le N∈SO n. Le M=M1. . . MkMk+1 ∈Su nbe he neighbo - hood sequence de ined in he p oo o P oposi ion 5. Pu Q′ =nk P i=1 bibi∈ Pi, i = 1,...,ko. Then Znis N-connec ed i and only i M< k+1(Z≥0)is a ull la ice in Rnand Q′ ep esen s all he cose s o M< k+1(Z≥0)in Zn. In Fig. 1 we conside he 2D-neighbo hood sequence N=N1N2N3N4∈Su 2, wi h Ni= (Pi, wi), whe e P1={(−1,0)},P2={(0,2),(3,2)},P3={(0,1)}, P4={(−2,−1),(1,1),(2,−1),(−1,−3)}and he weigh s a e a bi a y. 9 o e e y hwi h h∈ {1,..., }we ha e b0+ h X l=1 bil≤2|b0|+X b∈B |b|, whe e Bis he se {bj|j= 1, . . . , , bj6=b0}. PROOF. By Lemma 18 he e is a pe mu a ion (j0, j1,...,j ) o (0,1,..., ) such ha o e e y hwi h h∈ {0,..., }we ha e h P l=0 bjl≤ |b0|+P b∈B |b|. Le be he index o which j = 0 and pu il=     jl−1,i 1 ≤l < jl,i l≥ . Le h∈ {1,..., }. I h≥ hen b0+ h X l=1 bil= h X l=0 bjl≤ |b0|+X b∈B |b|. On he o he hand, i h < we ha e b0+ h X l=1 bil≤ |b0|+ h X l=1 bil=|b0|+ h−1 X l=0 bjl≤2|b0|+X b∈B |b|. This implies he s a emen . 2 Theo em 20 Le N=N1. . . NkNk+1 . . . Nl∈Su nwi h Ni= (Pi, wi) o i∈ {1,...,l}. Then he e is a ini e p ocedu e o decide whe he W(N)is symme ic on Zno no . PROOF. Fi s we in oduce some no a ion. Pu A ={a1+···+a ai∈Pi(i= 1,..., )} o 1 ≤ < l, and A=k−1 S =1 A ,B=l−1 S =k A . Mo eo e , se C={ak+1 +···+alai∈Pi(i=k+ 1,...,l)}. W i e R=P α∈C |α|+ 4 max a∈B{|a|}, and le Qdeno e he numbe o hose p∈Zn o which |p| ≤ Rholds. De ine he se Dby D={a+α1+···+αca∈A∪B, 0≤c≤2Q, αi∈C(i= 1,...,c)}. 16 Clea ly, Dis a ini e se . Hence by Theo em 14, we can check whe he W(b) = W(−b) holds o e e y b∈D∪(−D), o no . I no , hen Ndoes no induce a me ic. So assume ha Wis symme ic on D∪(−D). I Wis also symme ic on Zn (D∪(−D)), hen we a e done. Thus suppose ha W(b)6=W(−b) o some b∈Zn (D∪(−D)). Then, a sho es pa h om O o bis o he o m b=a+α1+α2+···+α wi h a∈B, ≥2Q+ 1 and αi∈C o i= 1,..., . Simila ly, a sho es pa h o −bis gi en by −b=a′+α′ 1+α′ 2+···+α′ ′wi h a′∈B, ′≥2Q+ 1 and α′ i∈C o i= 1,..., ′. We can u he assume ha + ′is minimal wi h he p ope y W(b)6=W(−b) (b6∈ D∪(−D)). Obse e ha W(a+α1+α2+···+α ) = ℓ(a) + ℓ(α1) + ℓ(α2) + ···+ℓ(α ) (13) o −2Q < ≤ and simila ly o a′+α′ 1+α′ 2+···+α′ ′. Mo eo e , obse e ha in he abo e o mulae we may pe mu e α1,...,α a bi a ily as well as α′ 1,...,α′ ′wi hou a ec ing he alidi y o he s a emen s. Now apply Co olla y 19 wi h b0=a+a′ o (a+a′) + α1+···+α +α′ 1+···+α′ ′=b+ (−b) = O. Then he e exis s a sequence i1,...,i + ′such ha α∗ 1,...,α∗ + ′is a pe mu a- ion o α1,...,α , α′ 1,...,α′ ′and a+a′+T P j=1 α∗ j≤4 max a∈B{|a|} +P α∈C |α|=R o T= 1,..., + ′. Since he e a e exac ly Q ec o s p∈Znwi h |p| ≤ R and by , ′>2Q, we ob ain he exis ence o Tand T′wi h 0 ≤T < T′≤Q such ha a+a′+T P j=1 α∗ j=a+a′+T′ P j=1 α∗ jwhich implies T′ P j=T+1 α∗ j=O. A e sui able pe mu a ions o α1,...,α and α′ 1,...,α′ ′, we may assume ha T′ P j=T+1 α∗ j=αs+1+···+α +α′ s′+1+···+α′ ′, whe e ≥s≥Q+1, ′≥s′≥Q+1, ( −s) + ( ′−s′) = T′−T≤Q. Hence a+α1+···+αs+a′+α′ 1+···+α′ s′=O.(14) F om he minimali y condi ion i ollows ha W(a+α1+···+αs) = W(a′+α′ 1+···+α′ s′),(15) hence by (13), ℓ(αs+1+···+α )6=ℓ(α′ s′+1+···+α′ ′) in iew o W(b)6=W(−b). By applying he abo e easoning o (14) we ob ain a e sui able pe mu a ion in ege s , ′wi h s≥ ≥1, s′≥ ′≥1, 0 <(s− ) + (s′− ′)≤Qand a+α1+···+α +a′+α′ 1+···+α′ ′=O. 17 F om (15) and he minimali y condi ion i ollows ha W(a+α1+···+α ) = W(a′+α′ 1+···+α′ ′), hence by (13) ℓ(α +1 +···+αs) = ℓ(α′ ′+1 +···+α′ s′).(16) Howe e , we can as well conside a+α1+···+α +αs+1 +···+α +a′+α′ 1+···+α′ ′+α′ s′+1 +···+α′ ′=O. By he minimali y condi ion we ha e W(a+α1+···+α +αs+1 +···+α ) = W(a′+α′ 1+···+α′ ′+α′ s′+1 +···+α′ ′). Compa ing his wi h W(b)6=W(−b), by (s− ) + (s′− ′)≤Qwe conclude ha ℓ(α +1 +···+αs)6=ℓ(α′ ′+1 +···+α′ s′) in con adic ion wi h (16). Hence he heo em ollows. 2 6.3 Me ici y By combining he esul s ob ained o he iangle inequali y and symme y wi h some addi ional obse a ions, we ob ain he ollowing s a emen . Theo em 21 Le N=N1. . . NkNk+1 . . . Nl∈Su nwi h Ni= (Pi, wi) o i∈ {1,...,l}. Then he e is a ini e p ocedu e o decide whe he Ninduces a me ic on Zno no . PROOF. Fi s we ha e o check whe he Znis N-connec ed. This can be done by a ini e p ocedu e acco ding o Theo em 11. F om Theo ems 17 and 20 we know ha he iangula and symme ic beha io o W(N) also can be checked by a ini e p ocedu e. So only he posi i i y o W(N) which emains o check. To es posi i i y, we do he ollowing. Le i∈ {1,...,l}be he maximal index o which o j= 1,...,i he e exis s a pj∈Pjsuch ha wj(pj) = 0. Then W(N) is posi i e i and only i we ha e pj=Owhene e wj(pj) = 0 o j= 1,...,i. Clea ly, his p ope y can be checked by a ini e p ocedu e. Hence he heo em ollows. 2 The ollowing co olla y ex ends he esul s o Das e al. [6] and Nagy [25] ob ained o pe iodic oc agonal and o gene al oc agonal neighbo hood se- quences, espec i ely, in he ini e dimensional case. 18 Co olla y 22 Suppose ha N= (Ni)∞ i=1 ∈Snwi h Ni= (Pi, wi), such ha N(j)⊒∗N o e e y j∈N,Znis N-connec ed, Niis symme ic, and wi(x)>0 o all x∈Pi {O}(i∈N). Then W(N)is a me ic on Zn. PROOF. Le Wdeno e he dis ance unc ion induced by N. The second pa o Theo em 15 gua an ees ha he iangle inequali y holds o W. All he o he necessa y p ope ies o me ici y ollow om ou assump ions. 2 Co olla y 23 Le N=N1∈Snwi h N1= (P1, w1). I Znis N-connec ed, N1is symme ic, and w1(x)>0 o all x∈P1 {O}, hen W(N)is a me ic on Zn. PROOF. The s a emen easily ollows om Co olla y 22 by no ing ha W(q, ;N(j)) = W(q, ;N) o all q, ∈Znand j∈Nin his case. 2 Co olla y 24 Le N= (Ni)∞ i=1 ∈SO nwi h Ni= (Pi, wi), such ha o e e y i∈N,Nioccu s in ini ely o en in N. Suppose ha Znis N-connec ed, Ni is symme ic, and wi(x)>0 o all x∈Pi {O}(i∈N). Then W(N)is a me ic on Zn. PROOF. As by ou assump ion he e is no neighbo hood Nioccu ing only ini ely many imes in N, P oposi ion 5 and i s p oo show ha he e exis s a cons an neighbo hood sequence Msuch ha W(N) is iden ical wi h W(M). Hence he s a emen ollows om Co olla y 23. 2 7 App oxima ing he Euclidean me ic The app oxima ion o he Euclidean dis ance by digi al me ics is a key p ob- lem in digi al geome y. In his sec ion we p esen some esul s owa ds his di ec ion. Yamashi a and Iba aki [30] showed ha o any N∈Sp n, i W(N) is a me ic hen he e exis c1, c2∈R>0such ha c1d(x;N)≤ ||x||2≤c2d(x;N) o any x∈Zn.(17) Now we in es iga e whe he he Euclidean dis ance can be mino a ed/majo a- ed o no in ou mo e gene al model. 19 P oposi ion 25 Le N∈Snand suppose ha W(N)is a me ic. Then he e exis s a c1∈R>0, such ha c1d(x;N)≤ ||x||2 o any x∈Zn. PROOF. In ac he p oo o Theo em 5 o Yamashi a and Iba aki [30] o pe iodic neighbo hood sequences can be ex ended o his case. Howe e , o he con enience o he eade , we ecall he main s eps o he p oo . Le c0= max d(e;N)e= (e1,...,en), ei∈ {0,1},n P i=1 ei= 1. No e ha c0>0, since W(N) is a me ic. Then d(x;N)≤c0 n P i=1 |xi|=c0||x||1 o any x= (x1,...,xn)∈Zn. I is well-known ha 1 √n||x||1≤ ||x||2. Thus c1d(x;N)≤ ||x||2wi h c1=1 c0√n.2 F om he ollowing example we can see ha he e exis s Nsuch ha he Euclidean dis ance canno be majo a ed in e ms o d(x;N), e en no wi h me ics gene a ed by ul ima ely pe iodic neighbo hood sequences. Example 26 Le n= 1,N1= (P, w1)wi h P={±1}and w1(±1) = 1, and le N2= (P, w2)wi h w2(±1) = 0. Conside N=N1N2∈Su 1. Then d(x;N) = 1 o any x∈Z(x6= 0), and hus he e exis s no c2∈R>0such ha ||x||2≤c2d(x;N) o any x∈Z. The nex wo p oposi ions show ha p ope y (17) holds unde sui able mild condi ions. P oposi ion 27 I N∈SO ninduces a me ic on Zn, hen he e exis s a c2∈ R>0such ha ||x||2≤c2d(x;N) o any x∈Zn. PROOF. Theo em 8 and i s p oo gua an ee ha he e exis s a cons an (pe- iodic) neighbo hood sequence, which gene a es he same me ic as N. Since he s a emen holds o pe iodic sequences (see [30]), he p oo is comple e. 2 P oposi ion 28 Le N=N1. . . NkNk+1 . . . Nl∈Su nwi h Ni= (Pi, wi) o i∈ {1,...,l}such ha W(N) =: d(N)is a me ic. Then he e exis s a c3∈R>0such ha ||x||2≤c3d(x;N) o e e y x∈Zn i and only i ℓ(s)>0 o e e y s∈Q∞ {O}, whe e Q∞is de ined in Theo em 11. 20 PROOF. We may assume wi hou loss o gene ali y ha N=N1. . . NkNk+1 wi h Ni= (Pi, wi) o i= 1,...,k+ 1 using P oposi ion 7. Thus o p o e he s a emen , we can eplace he condi ion ”ℓ(s)>0 o e e y s∈Q∞ {O}” by ”wk+1(y)>0 o e e y y∈Pk+1 {O}”. Fi s we p o e necessi y. Suppose ha he e exis s a y∈Pk+1 {O}such ha d(y) = 0. Conside an a bi a y pa h s= [O, x1,...,xk] ( he emp y pa h i k= 0) and con inue his pa h by always selec ing y∈Pk+1 om he neighbo hood Nk+1. Using his pa h we can mo e a bi a ily a om he o igin wi h espec o he Euclidean dis ance. Howe e , all he poin s on he pa h ha e leng h a mos ℓ(s). This means ha we canno majo a e he Euclidean dis ance, and p o es he necessi y pa . To p o e su iciency assume ha wk+1(y)>0 o e e y y∈Pk+1 {O}. Pu b1= min (ℓ(s) ||s||2 s∈ k [ =1 ( X i=1 uiui∈Pi, i = 1,..., )), b2= min (wk+1(y) ||y||2 y∈Pk+1 {O}), and pu b3= min{b1, b2}. No e ha b3>0, since d(N) is a me ic and wk+1(y)>0 o e e y y∈Pk+1 {O}. Le xbe an a bi a y poin o Zn, and conside a sho es N-pa h om O o x,O=q0,...,q =xsay. I ≤k hen ||x||2≤1 b1d(x;N). O he wise, d(x;N) = ℓ([O,...,qk])+ P i=k+1 wk+1(qi−qi−1)≥ b1||qk||2+b2 P i=k+1 ||qi−qi−1||2≥b3||x||2. Hence c3d(x;N)≥ ||x||2wi h c3=1 b3, and he p oo is comple e. 2 8 Applica ions Neighbo hood sequences ha e al eady been applied success ully o p ac ical image p ocessing pu poses like segmen a ion [20], and e ie al [22]. In his sec ion we show how ou cu en esul s can be used in he heo y o dis ance ans o ma ions. On one hand we indica e how ul ima ely pe iodic neighbo - hood sequences can p o ide a new ool in some well-known image p ocessing p ocedu es. On he o he hand we p esen an applica ion scheme o neigh- bo hood sequences om SO n. 21 8.1 Dis ance ans o ma ions Dis ance ans o ma ions p o ide a e y use ul basis o many image p ocess- ing p oblems. To indica e how widely his echnique is applied, we e e o [2,4,14,28] and he e e ences gi en he e as cha ac e is ic examples. Usually he classical amilies o dis ance ans o ma ions (n-Neighbo , cham e , oc ag- onal, D-Euclidean) a e conside ed in applica ions. These amilies a e deeply in es iga ed by Bo ge o s in [1]. These dis ance ans o ma ions a e based on a mask o gi en size (e.g. 3×3 o 5×5 in Z2), wi h ce ain non-nega i e weigh s assigned o he en i ies o he mask. Fo example, Fig. 2 shows he gene al 3×3 mask used by Bo ge o s in [1] o compose a ious dis ance ans o ma ions. Fig. 2. Classical 3×3 mask ope a o o dis ance ans o ma ions wi h non-nega i e weigh s d1,d2. Using his mask, he dis ance o wo poin s o he domain is calcula ed jus as in ou model, by conside ing a cons an neighbo hood sequence N=M, whe e he neighbo hood Mis he mask o he dis ance ans o ma ion oge he wi h he assigned weigh s. No e ha he dis ance ans o ma ion amilies in es iga ed by Bo ge o s [1] a e special cases o he model gi en by Yamashi a and Iba aki in [30], who used pe iodic neighbo hood sequences. Howe e , Yamashi a and Iba aki [30] showed ha i he dis ance unc ion gene a ed by a pe iodic neighbo hood sequence is a me ic hen he pe iodic sequence is equi alen o a cons an sequence (wi h espec o he gene a ed dis ance unc ions). Thus we ye again ha e a cons an sequence i he impo an p ope y o me ici y is equi ed. Ul ima ely pe iodic sequences p esen ed in ou model ob iously co e pe iodic ones and hus also he classical amilies in [1]. Hence he use o such sequences opens up new possibili ies o achie e mo e gene al dis ance ans o ma ions. We unde line Example 6 which shows ha ul ima ely pe iodic sequences can- no be eplaced by cons an ones, e en i me ici y is equi ed. Especially, as a key p oblem, we men ion he amous esul s o Bo ge o s [1] abou inding sui able weigh s o a dis ance ans o ma ion o app oxima e he Euclidean dis ance. I is na u al o expec ha in ou mo e gene al model be e app ox- ima ions can be ound o he Euclidean me ic han in case o using cons an sequences. 22 8.2 Op imal usage o esou ces We show an applica ion scheme o demons a e he impo ance and applica- bili y o ou esul s abou SO n. Using sequences belonging o SO n, in ui i ely we ha e he oppo uni y o igno e undesi ed elemen s o he sequence, by doing no hing o no cos a a s ep (by using Owi h weigh 0). Mo eo e , we do no ha e o deal wi h he o de o he neighbo hoods in he sequence when inding a sho es pa h be ween wo poin s, as acco ding o Rema k 4 and P oposi ion 5 he elemen s o such sequences can be eely pe mu ed. In gene al, we can in e p e his case as i we ha e esou ces wi h gi en cos s, such ha some o he esou ces can be used only a p esc ibed numbe o imes, while o he s in ini ely o en. Mo e p ecisely, we can hink o mo ing in he space. Suppose ha ou ask is o ind an op imal pa h o ou des ina ion. I we know which pa h would be op imal hen ega dless o he o de , we can pick up he desi ed ec o s eely and build up ou pa h. To make ou ideas mo e clea we conside a conc e e example. Le he neigh- bo hoods N1, N2, N3, N4be as shown in Figu e 3(a), whe e he black discs ep esen he neighbo hood ec o s and he alues inside hei weigh s. Le N=N1N2N3N4N1{Ni}∞ i=5 be any sequence such ha Ni∈ {N3, N4} o i≥5, wi h bo h Ni=N3and Ni=N4in ini ely o en. Then clea ly, N∈SO 2. Now, as i can be seen also in Figu e 3(b), o each (2,2) om he o igin we can ake O, (1,0), Oand (1,2) om N1,N2,N3and N4, espec i ely, o ob ain he sho es pa h. In o he wo ds we can ”skip” N1and N3, and use N2and N4 eely o build up he pa h. Using P oposi ion 5 we can de e mine an ul ima ely cons an neighbo hood sequence N′equi alen o N. This sequence is gi en by N′=N1N1N2N0, whe e N0is shown in Figu e 3(c). When in es iga ing me ici y, we can es ic ou a en ion om he gene al case o ul ima ely pe iodic sequences. To see his, conside a (no necessa ily ul ima ely pe iodic) neighbo hood sequence om SO n. Le N1, N2,...,Nkbe he neighbo hoods which occu only ini ely o en wi h he igh mul iplici- ies, and Nk+1,...,Nl he neighbo hoods which occu in ini ely o en. Then, as shown in he pape , he me ical p ope ies o he sequence a e he same as o N1N2. . . NkNk+1 . . . Nl. So we can apply he heo y in he pape o ul ima ely pe iodic sequences o s udy he me ical p ope ies o such neigh- bo hood sequences. We may e en combine N1. . . Nk o one neighbo hood and Nk+1 . . . Nl o ano he o simpli y o mulas, bu hen we loose con ol on he sizes o he neighbo hoods as shown abo e. 23 (a) (b) (c) Fig. 3. Choosing op imal neighbo hood elemen s o ob ain a sho es pa h using a sequence N∈SO 2; (a) he elemen s o N, (b) he sho es pa h o (2,2) using N2and N4, (c) he neighbo hood o compose he equi alen ul ima ely cons an sequence N′=N1N1N2N0. 9 Conclusion Since he i s submission o he pape , he au ho s wen on wi h hei esea ch ega ding neighbo hood sequences. As co esponding esul s, we highligh he de i a ion o in ege alues o be used in cham e ing o app oxima e he Eu- clidean me ic [19,29], he applica ion o ul ima ely pe iodic neighbo hood sequences in image e ie al [22], and he applica ion o weigh ed neighbo - hoods o app oxima e non me ical Minkowski dis ances [21]. We also no e ha he complexi y analysis o he ini e p ocedu es we ha e gi en o decide on se e al p ope ies ega ding neighbo hood sequences has been le as an open issue. Acknowledgmen The au ho s a e g a e ul o he e e ees o hei ho ough wo k and aluable commen s. 24 Re e ences [1] G. Bo ge o s: Dis ance ans o ma ions in a bi a y dimensions, Compu . Vision G aphics Image P ocess. 27 (1984), 321-345. [2] G. Bo ge o s: Hie a chical cham e ma ching: a pa ame ic edge ma ching algo i hm, IEEE T ansac ions on Pa e n Analysis and Machine In elligence, 10(6) (1988), 849-865. [3] P.E. Danielsson: 3D oc agonal me ics, Eigh h Scandina ian Con . Image P ocess., 1993, pp. 727-736. [4] P.E. Danielsson: Euclidean dis ance mapping, Compu e G aphics and Image P ocessing,14 (1980), 227-248. [5] P.P. Das: Bes simple oc agonal dis ances in digi al geome y, J. App ox. Theo y 68 (1992), 155-174. [6] P.P. Das, P.P. Chak aba i and B.N. Cha e ji: Dis ance unc ions in digi al geome y, In o m. Sci. 42 (1987), 113-136. [7] P.P. Das, P.P. Chak aba i and B.N. Cha e ji: Gene alised dis ances in digi al geome y, In o m. Sci. 42 (1987), 51-67. [8] P.P. Das and B.N. Cha e ji: Es ima ion o e o s be ween Euclidean and m- neighbo dis ance, In o m. Sci. 48 (1989), 1-26. [9] P.P. Das and B.N. Cha e ji: Hype sphe es in digi al geome y, In o m. Sci. 50 (1990), 73-91. [10] P.P. Das and B.N. Cha e ji: Oc agonal dis ances o digi al pic u es, In o m. Sci. 50 (1990), 123-150. [11] A. Fazekas: La ice o dis ances based on 3D-neighbou hood sequences, Ac a Ma h. Acad. Paedagog. Nyh´azi. 15 (1999), 55-60. [12] A. Fazekas, A. Hajdu and L. Hajdu: La ice o gene alized neighbou hood sequences in nD and ∞D, Publ. Ma h. Deb ecen 60 (2002), 405-427. [13] R. Ga inkel and G.L. Nemhause : In ege P og amming. John Wiley and Sons, New Yo k, 1972. [14] Y. Ge and J.M. Fi zpa ick: On he gene a ion o skele ons om disc e e euclidean dis ance maps., IEEE T ansac ions on Pa e n Analysis and Machine In elligence,18 (1996), 1055-1066. [15] J.H. G ace and A. Young: The Algeb a o In a ian s. New Yo k: Chelsea, 1965. [16] A. Hajdu: Geome y o neighbou hood sequences, Pa e n Recogni ion Le . 24/15 (2003), 2597-2606. [17] A. Hajdu and L. Hajdu: Veloci y and dis ance o neighbou hood sequences, Ac a Cybe ne . 16 (2003), 133-145. 25