EUCLIDEAN VORONOI LABELING ON THE MULTIDIMENSIONAL GRID

Given a set of k points (sites) S subset-of R(d), and a finite d-dimen sional grid G(n)d = {1, n}d, we describe an efficient algorithm comput ing the mapping D: G(n)d --> {1,...,k} such that D(p) is the index of the site closest to p under the Euclidean norm. This mapping is called the Voronoi labelling of the grid. The algorithm traverses the points of G on a ''locality-preserving'' space-filling curve, exploiting the correlation between the value of D on adjacent grid points to reduce computation time. The advantage of this algorithm over existing ones i s that it works in any dimension, and is general-purpose, in the sense that it is easily modified to accomodate many variants of the problem , such as non-integral sites, and computation on a subset of G. The ru ntimes of our algorithm in two dimensions compare with those of the ex isting algorithms, and are better than the few existing algorithms ope rating in higher dimensions.