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

Reprinted from Sadhana 18(1993), P. P. Das and B. N. Chatterji, Digital Distance Geometry: A Survey , 159-187,
Copyright (1993), with permission from Indian Academy of Sciences.

FIGURE 2.4: A minimal O(2) or 18-path between two points (2,-7,5) and
(-8,-4,13) in 3-D.

∩Neb(y;N(·)), is chosen if Π ∗ (y,0) is a concatenation
of Π ∗ (y,z) and Π ∗ (z,0) (evidently, |Π ∗ (y,0)| = |Π ∗ (y,z)| + |Π ∗ (z,0)|). In
Algorithm 3 we illustrate such a choice for O(m)-neighborhood set for d m
distance.

the algorithm, z ∈ Σ n

2.2.3 Distances and Metrics
In Z n , Euclidean distance E n is defined as follows:
Definition 2.11. In n-D, E n : Z n × Z n → R + ∪ {0} is the Euclidean
distance where ∀u,v ∈ Z n , E n (u,v) =

n
i=1 (u(i)−v(i)) 2 €
From Euclidean geometry, we know that the length of the shortest path
(that is, a straight line joining two points) is given by the Euclidean distance.
A similar result holds for various neighborhood-defined paths in digital n-D
geometry. Once we define a neighborhood, the resulting shortest path between
two points has a length that is represented by a nice closed form distance
function that gives the length of the shortest path in terms of the coordinates
of the two points and the parameters of the neighborhood set.
A distance function usually has this property of representing the length of
the shortest path, provided it is a metric in the following sense.
Definition 2.12. A distance function d : Z n × Z n → R + ∪{0} is called a
metric if ∀u,v,w ∈ Z n ,

1. d is a total: d(u,v) is defined and finite.