Euclidean Voronoi labelling on the multidimensional grid

Craig Gotsman, Michael Lindenbaum

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


Given a set of k points (sites) S ⊂ Rd, and a finite d-dimensional grid Gnd=(I, n)d, we describe an efficient algorithm computing the mapping D : Gnd → {l...,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 is 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 runtimes of our algorithm in two dimensions compare with those of the existing algorithms, and are better than the few existing algorithms operating in higher dimensions.

Original languageEnglish (US)
Pages (from-to)409-415
Number of pages7
JournalPattern Recognition Letters
Issue number4
StatePublished - Apr 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


  • Grid
  • Space-filling curve, Hilbert curve
  • Voronoi diagram


Dive into the research topics of 'Euclidean Voronoi labelling on the multidimensional grid'. Together they form a unique fingerprint.

Cite this