In 2003, Mauer * at al.* published a paper describing an algorithm that computes the exact distance transform in linear time (with respect to image size) for the rectangular binary images in the k-dimensional Euclidean space 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 discuss the computational time savings associated with them. All these 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 the exact value of the distance from the
geometrically defined object boundary. We provide a complete proof (which was not given Mauer * at al.* paper of 2003) that all these algorithms work correctly for
L_{p}-metric with 1 < p< &infin. We also point out that the precise form of the algorithm from is not well defined for L_{1} and L_{&infin} metrics. In addition, we show that the algorithm can be used to find, in linear time, the exact value of the diameter of an object, that is, the largest possible distance between any two of its elements.

**SPIE Conference Proc. version.**

MIPG Technical Report
**# 337 version (with some errors).**

**Last modified January 22, 2011.**