Fast computation of the Euclidian distance maps for binary images
Mihail N. Kolountzakis, Kiriakos N. Kutulakos · Information Processing Letters · 1992
A simple algorithm is given for the computation of the Euclidian distance from the set of black points in an N × N black and white image, for all points in the image. The running time is O(N2 log N) and O(N) extra space is required. The algorithm is suitable for implementation on a parallel machine.