基于Voronoi图的最近邻查询的索引结构的研究

基于Voronoi图的最近邻查询在计算几何中已被研究了相当长一段时间。但在以往的研究中,基于Voronoi图的最近邻查询究竟是基于何种具体的索引结构去实现对查询空间的搜索的,却很少被提及。本文把传统的R树和Voronoi图在解决最近邻查询问题中的优越性相结合,提出了一种新的索引结构:VR树。进而提出了基于VR树索引结构的NN查询算法并对这该算法进行分析,在理论上证明了这个算法较基于R树索引结构的最近邻查询算法优。

Research on index of nearest neighbors queries based on Voronoi diagrams

The nearest neighbor inquiry is foundational and important in both mobile computing research and real life applications.Nearest neighbor inquiry based on Voronoi diagrams has been studied for quite a long time in Computational Geometry.Which concrete index structure to inquire the spatial search used in the nearest neighbor inquire based on the Voronoi diagram in the past research is rarely mentioned.In this paper a new index structure VR-tree is presented,which combines the advantage of Voronoi diagram in the field of resolving nearest neighbor inquiry with the traditional R-tree.Then proposed a NN inquiry algorithm which is based on VR-tree index structure.It has been proved in theory that it is superior to the algorithm of neighbor inquiry which based on R-tree index structure.