Fast parallel algorithm for distance transform

We present an O((log log N)²) -time algorithm for computing the distance transform of an N × N binary image. Our algorithm is designed for the common concurrent read concurrent write parallel random access machine (CRCW PRAM) and requires O(N^2+ε/log log N) processors, for any ε such that 0 < ε < 1. Our algorithm is based on a novel deterministic sampling scheme and can be used for computing distance transforms for a very general class of distance functions. We also present a scalable version of our algorithm when the number of processors is available p^2+ε/log log p for some p < N. In this case, our algorithm runs in O((N²/p²)+(N/p) log log p + (log log p)²) time. This scalable algorithm is more practical since usually the number of available processors is much less than the size of the image.