Theory of Computing ------------------- Title : Distance Transforms of Sampled Functions Authors : Pedro F. Felzenszwalb and Daniel P. Huttenlocher Volume : 8 Number : 19 Pages : 415-428 URL : https://theoryofcomputing.org/articles/v008a019 Abstract -------- We describe linear-time algorithms for solving a class of problems that involve transforming a cost function on a grid using spatial information. These problems can be viewed as a generalization of classical distance transforms of binary images, where the binary image is replaced by an arbitrary function on a grid. Alternatively they can be viewed in terms of the minimum convolution of two functions, which is an important operation in grayscale morphology. A consequence of our techniques is a simple and fast method for computing the Euclidean distance transform of a binary image. Our algorithms are also applicable to Viterbi decoding, belief propagation, and optimal control.