Voronoi图的构建与受限区域内的最近邻查询方法研究

Research on Methods of Construction of Voronoi Diagram and Nearest Neighbor Query in Constrained Regions

Voronoi图在空间数据查询、数据挖掘、图像处理、模式识别和智能交通管理等方面具有重要的作用。为了简化构建的复杂性和提高构建效率,基于分治法、启发式局部优化策略和局部数据点的扫描线动态更新策略,提出了基于凸包的Voronoi图生成方法,给出了Create_Voronoi()算法。进一步,为了弥补已有近邻查询方法无法处理受限区域内的最近邻查询的不足,基于Voronoi图研究了受限区域内的同质和异质最近邻查询方法,分别提出了TVor_NN()算法和YVor_NN()算法。理论研究和实验分析表明,提出的研究方法在Voronoi图的构建和受限范围的最近邻查询等方面具有较大的优势。

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.