3-D Voronoi tessellation algorithms

摘要

We consider the discrete Voronoi diagram in the three-dimensional space, that is, the Voronoi tessellation of a 3-D binary image. The input to the tessellation algorithm is a 3-D image containing a set of pixels of value 0 (generators). The goal is to classify the rest of the pixels to the nearest generator. This paper gives a simple algorithm for computing the Voronoi tessellation map of a 3-D binary image. It runs in O(N-3) time for an N x N x N input image. A hardware algorithm is also presented, which computes the 3-D Voronoi tessellation map in O(N-2) time on an O(N-3)-cell array.