An O(1) time algorithm for the 3D euclidean distance transform on the CRCW PRAM model
In this paper, we develop a parallel algorithm for the 2D Euclidean distance transform (2D-EDT, for short) of a binary image of size N x N in O(1) time using N(2+delta+epsilon) CRCW processors and a parallel algorithm for the 3D Euclidean distance transform (3D_EDT, for short) of a binary image of size N x N x N in O(1) time using N(3+delta+epsilon) CRCW processors, where delta = 1/k epsilon = 1/2(c+1)-1, k, and c 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+delta+epsilon) (N(3+delta+epsilon)) CRCW processors. To the best of our knowledge, all results derived above are the best O(1) time algorithms known.
euclidean distance transform crcw pram model parallel algorithm voronoi diagram computer vision image processing