The Gradient Voronoi Diagram and Construction Algorithm

Taking the growing processing results as angles, an ordinary Voronoi diagram and weighted Voronoi diagram are produced at uniform speed on an ideal Euclidean plane. However, based on analysis, modeling is not always sound in that a Voronoi diagram progresses at varying velocities on a non-ideal plane. The anisotropic non-ideal plane is depicted by weight distance and the growth velocity is formalized in a form conforming to the time derivative of weight distance. Therefore, a new Voronoi diagram, namely Gradient Voronoi Diagram (GVD) was defined in this paper. Taking the gradient caused by changes in elevation as an example, a typical construction model for GVD was propounded with the help of the dilation operator for mathematical morphology in raster space. An analysis shows that GVD has better guided significance and practical application value in the expression of influence regions and the Voronoi adjacency relationship.