Abstract: The exiting methods of the nearest neighbor query can not search the simple continuous near neighbor chain in the constrained regions. To remedy the deficiency of the existing work, according to the complexity of the constrained regions and the obstacles, the simple continuous near neighbor chain query with non obstacles and with obstacles were studied respectively. The VOR_NB_CRSCNNC algorithm and the VOR_CB_CRSCNNC algorithm were presented. The spatial data were filtered and computed based on the Voronoi diagram and the judging circles. The calculations of each query were reduced by only considering the points which lay in the Voronoi polygon and the juding circles. The theatrical study and the experimental results show that the redundant calculation is reduced and the query efficiency is less affected by the constrained regions.

Key words: spatial database, Voronoi diagram, nearest neighbor query, Simple Continues Near Neighbor Chain (SCNNC), constrained region

摘要： 由于已有的最近邻查询方法无法直接处理受限区域内的单纯型连续近邻链查询问题，针对受限区域和障碍物的复杂性，详细研究了受限区域内无障碍物和有障碍物环境下的单纯型连续近邻链查询方法，分别提出了VOR_NB_CRSCNNC算法和VOR_CB_CRSCNNC算法。算法基于计算几何中的Voronoi图和判定圆域对空间数据对象进行预先筛选和计算，每次查询仅需考虑落在数量较少的Voronoi多边形和判定圆域内的数据点，预先过滤掉大量数据，减少每次计算涉及的数据量。理论研究和实验分析表明，所提出的算法在查询过程中减少了数据逐一判断的冗余计算，受受限区域形状的影响较小，较大程度提高了查询效率。

关键词: 空间数据库, Voronoi图, 最近邻查询, 单纯型连续近邻链, 受限区域