Efficient algorithms for the k-distance transformation

The k-distance transformation (k-DT) computes the k nearest patterns from each location on a discrete regular grid within a D dimensional volume, which Warfield [Patt. Rec. Letters, 17(1996) 713-721] proposed to implement using 2^D raster scans. We investigate the possible approaches for efficient implementations by extending the existing Euclidean 1-DT methods and propose two new k-DT algorithms. The first is based on ordered propagation while the second divides the problem into D 1-dimensional problems. We compare the computational complexity of the different approaches.