## Abstract

Given a set of k points (sites) S ⊂ R^{d}, and a finite d-dimensional grid G_{n}^{d}=(I, n)^{d}, we describe an efficient algorithm computing the mapping D : G_{n}^{d} → {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 language | English (US) |
---|---|

Pages (from-to) | 409-415 |

Number of pages | 7 |

Journal | Pattern Recognition Letters |

Volume | 16 |

Issue number | 4 |

DOIs | |

State | Published - Apr 1995 |

Externally published | Yes |

## 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