A Fast and Efficient Algorithm for Construction of Discrete Voronoi Diagram

Unlike the cells of a Voronoi diagram in the real space the cells of a discrete Voronoi diagram in the discrete space has finite number of points. Hence in the literature we find a significant difference in the approach to the construction of the discrete voronoi diagram as compared to the construction of the Voronoi Diagram in the real space. In the discrete space the construction of discrete Voronoi diagram for a set of given sites is the process of assigning each pixel in the discrete space to its nearest site. Although there are many algorithms for the construction of discrete Voronoi diagram using the above mentioned approach, none of these algorithms found in the literature take into consideration the geometrical properties of the Voronoi Diagram while constructing it. We present a novel approach for the construction of discrete Voronoi Diagram for a given set of points based on a purely digital geometric approach taking into consideration its geometry. Since the circle is defined as the locus of a point that is equidistant from a given point, our algorithm constructs digital circles around each site, to assign the pixels that are nearest to that site using an iterative circle growing technique. The key idea of the proposed algorithm is that in the i-th iteration (initially \(i=1\) ) we assign pixels which are at a distance given by the open interval \((i-\frac{1}{2}, i+\frac{1}{2})\) from each site, provided, they are not already assigned to any other site. Thus, at any instant of time a pixel, p is assigned to a site s if and only if s is its nearest site in the digital space. Our algorithm terminates once all pixels have been assigned to the nearest site.