New methods for the construction of Voronoi Diagram and the nearest neighbor query

The existing methods for the construction of Voronoi Diagram and the nearest neighbor query have several disadvantages. In view of the disadvantages, the new methods were studied in detail. To construct the Voronoi diagram effectively, the datasets were grouped in advance, and then the divide-and-conquer method combined with the increment method was used to generate Delaunay triangulation. By generating the Voronoi diagram from Delaunay triangulation, the Creat_Vor algorithm was proposed. In order to effectively query and update the nearest neighbors of the given points, the methods based on the spatial grids and the Voronoi diagram were studied. The VGride_NN algorithm and VGride_BNN algorithm were put forward. Theory and experiments show that the new methods have advantages in dealing with the dynamic dataset.