The Euclidean Distance Transform is an important computational tool for the processing of binary images, with applications in many areas such as computer vision, pattern recognition and robotics. We investigate the properties of this transform and describe an O(n2) time optimal sequential algorithm. A deterministic EREW-PRAM parallel algorithm which runs in O( log n) time using O(n2) processors and O(n2) space is also derived. Further, a cost optimal randomized parallel algorithm which runs within the same time bounds with high probability, is given.