Lecture notes in computer science: research on hybrid grid algorithm of voronoi diagram

Abstract

Characteristics and performance of two grid methods, which include the growth method and the point by point scanning method of Voronoi diagram, are analyzed qualitatively and quantitatively. The theoretical analysis and experimental results show that the growth method is faster, but the boundary of Voronoi diagram generated by the point by point scanning method is more accurate. By combining the advantages of these two grid methods, the hybrid grid algorithm is proposed: the growth method is used firstly to extend a large step, and then the point by point scanning method is used to color the remaining blank pixel. The theoretical analysis and experimental results show that the speed of the hybrid grid algorithm is close to the fastest growth algorithm, and the accuracy is as well as the point by point scanning algorithm.