Abstract: The Voronoi diagram plays an important role in spatial data query,data mining,image processing,pattern recognition and intelligent traffic management etc．To reduce complexity and improve efficiency,based on the divide and conquer,local optimization and dynamic update of scan lines,the method to construct Voronoi diagram using the convex hulls was proposed．The Create_Voronoi() algorithm was given．Furthermore,to remedy the defects of the existing methods for the near neighbor query,the identical -quality nearest neighbor query and the heterogeneous nearest neighbor query in the constrained regions were studied．The TVor_NN() algorithm and the YVor_NN () algorithm were presented．The theatrical study and the experimental results show that the redundant calculation is reduced and the algorithms hold large advantage at the construction of Voronoi diagram and the nearest neighbor query in constrained regions.

Key words: Voronoi diagram,Delaunay triangle,Nearest neighbor query,Constrained region