Distance Functions in Digital Geometry - Digital Geometry in Image Processing - page 46

Algorithm 3: TRACE(x, n, m): Trace an O(m)-path from 0 to x
Require: x ∈ Σ n
y ← x
length← 0
print x
while y = 0 do
for 1 ≤ i≤ m do
if y i = 0 then
y i ← y i −1 // Choice of next point
end if
end for
length← length + 1
print y
end while
print length

• Prove that Algorithm 3 traces a shortest O(m)-path.

• Prove that the length of the path is given by the expression of d m .

Proof proceeds by induction on the path length and relies on the fact that
if w is a point on a shortest path Π

∗ ∗

(u,v;m : n), then Π (u,w;m : n) and

∗

Π (w,v;m : n) are both shortest paths between respective points and use the

same sequence of points as in Π

∗

(u,v).

2.3.1.2 m-Neighbor Distance in Real Space
We relax the integral constraints from d m to generalize it further over the
n-D real space R n . We call it the real m-neighbor distance δ m [66]. In
δ m , m is any positive real value less than n, and δ m itself is allowed to be
non-integral.

Definition 2.17. ∀n, and ∀x,y ∈ R n ,δ m : R n ×R n → R + ∪{0} is defined
as:

n
i=1

|x i −y i |
m

max
i=1

δ m (x,y) = max(

|x i −y i |, ).

Clearly δ m (x,y) = δ m (x −y,0) = δ m (x−y).

€

The following results are proved in [66]:

Theorem 2.5. δ m is a metric over R n .

€

Theorem 2.6. ∀x,y ∈ R n

1. ∀,m≥ n,δ m (x,y) = δ n (x,y) = max i=1

|x i −y i |,