Study On Fast Generating Algorithm For Higher-Order Voronoi Diagram

Higher-order Voronoi diagram is an important generalization of ordinary Voronoi diagram. It has widespread applications in the problem of finding k-nearest neighbors in a planar point set. However, the previous algorithms of constructing higher-order Voronoi diagram have complex data structure and high time complexity. Due to these features higher-order Voronoi diagram is limited in practical use. This article introduces the definition and properties of k-nearest (1≤k