In 2003, Maurer * at al.* published a paper
describing an algorithm that computes the exact distance transform
in a linear time (with respect to image size)
for the rectangular binary images in the k-dimensional space **R**^{k} and distance
measured with respect to L_{p}-metric for 1 ≤ p ≤ &infin, which includes
Euclidean distance L_{2}. In this paper we discuss this algorithm from theoretical
and practical points of view. On the practical side, we concentrate on
its Euclidean distance version, discuss the possible ways of implementing it as signed distance transform,
and experimentally compare implemented algorithms.
We also describe the parallelization of these algorithms and the computation time savings associated with such an implementation.
The discussed implementations will be made available as a part of the CAVASS software system
developed and maintained in our group.
On the theoretical side, we prove that our version of the signed distance transform algorithm, *GBDT*,
returns, in a linear time, the *exact* value of the distance from the *geometrically defined object boundary.*
We notice that, actually, the precise form of the algorithm fromMaurer * at al.*
is not well defined for L_{1} and L_{&infin} metrics
and point to our complete proof (not given in Maurer * at al.*)
that all these algorithms work correctly for the L_{p}-metric with 1 < p < &infin.

**Conference Proceeding reprint.**

**Last modified May 13, 2009.**