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