Euclidean Voronoi labelling on the multidimensional grid

Craig Gotsman, Michael Lindenbaum

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

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
Volume16
Issue number4
DOIs
StatePublished - Apr 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

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

Fingerprint

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

Cite this