We present parallel algorithms for the Distance Transformation (DT) with the City Block (CB) distance measure. They are 'divide-and-conquer' algorithms operating on an image that is divided into subregions. Locally calculated partial DTs are combined into global information from which the global DT can be calculated locally. The computational complexity of the two local phases is proportional to the number of subregion pixels. The execution time of the combination step varies, depending on the combining strategy, from proportional to the image perimeter to proportional to the subregion perimeter.