Parallel Algorithms for Higher-Dimensional Euclidean Distance Transforms with Applications

Yuh-Rau WANG  Shi-Jinn HORNG  Yu-Hua LEE  Pei-Zong LEE  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.9   pp.1586-1593
Publication Date: 2003/09/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED PAPER (Special Issue on Parallel and Distributed Computing, Applications and Technologies)
Category: Algorithms and Applications
Keyword: 
Euclidean distance transform,  parallel algorithm,  Voronoi diagram,  proximate point,  EREW PRAM,  CRCW PRAM,  medial axis transform,  

Full Text: PDF>>
Buy this Article




Summary: 
Based on the dimensionality reduction technique and the solution for proximate points problem, we achieve the optimality of the three-dimensional Euclidean distance transform (3D_EDT) computation. For an N N N binary image, our algorithms for both 3D_EDT and its applications can be performed in O (log log N) time using CRCW processors or in O (log N) time using EREW processors. To the best of our knowledge, all results described above are the best known. As for the n-dimensional Euclidean distance transform (nD_EDT) and its applications of a binary image of size Nn, all of them can be computed in O (nlog log N) time using CRCW processors or in O (nlog N) time using EREW processors.