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.