Multidimensional Distance Transforms using the FEED-class Algorithm

Abstract

The Fast Exact Euclidean Distance transform (FEED) algorithm is extended beyond two dimensions. 3D-FEED is introduced, followed by nD-FEED. The nD-FEED algorithm uses the inverse approach from the naive DT algorithms and works with exact euclidean distances. The timecomplexity of nD-FEED is proven to be exponential in the amount of dimensions: