A parallel algorithm for weighted distance transforms

This paper presents a parallel algorithm for the weighted distance transform and the nearest feature transform of an n×n binary image. We show that the algorithm runs in O(log n) time using n² /log n processors on the EREW PRAM and in O(log log n) time using n²/log log n processors on the common CRCW PRAM. We also show that the algorithm runs in O(n²/p²+n) time an a p×p mesh and in O (n²/p²+(n log p)/p) time on a p² processor hypercube (for 1⩽p⩽n). The algorithm is cost optimal on the PRAMs, on the mesh (for 1⩽p⩽√n) and on the hypercube (for 1⩽p⩽n/log n). We show that the time complexity on the EREW PRAM is time optimal