An O(1) time algorithm for the 3D Euclidean distance transform on the CRCW PRAM model

We develop a parallel algorithm for the 2D Euclidean distance transform (2D_EDT, for short) of a binary image of size N × N in O(1) time using N^2+δ+ε CRCW processors and a parallel algorithm for the 3D Euclidean distance transform (3D_EDT, for short) of a binary image of size N × N × N in O(1) time using N^3+δ+ε CRCW processors, where δ=1/, ε=1/(2^c+1-1), h, and are constants and positive integers. Our 2D_EDT (3D_EDT) parallel algorithm can be used to build up Voronoi diagram and Voronoi polygons (polyhedra) in a 2D (3D) binary image also. All of these parallel algorithms can be performed in O(1) time using N^2+δ+ε (N^3+δ+ε) CRCW processors. To the best of our knowledge, all results derived above are the best O(1) time algorithms known.