障碍空间中基于Voronoi图的组反k最近邻查询研究

来源：计算机研究与发展杂志2017年第4期北京时间：

作者：张丽平,刘蕾,郝晓红,李松,郝忠孝,

摘要：为了解决已有研究成果无法有效处理障碍空间中的组反k最近邻查询问题，提出了障碍物环境中基于Voronoi图的OGRkNN查询方法,该方法获得的结果集是将一组查询点中任意一点作为障碍kNN的数据点集合，在实际应用中可以用来评估一组查询对象的影响力.依据障碍物集合是否发生变化提出了2种情况下的OGRkNN查询方法，一种是静态障碍物环境下的OGRkNN查询(简称STA_OGRkNN查询)方法，另一种是动态障碍物环境下的OGRkNN查询(简称DYN_OGRkNN查询)方法.其中STA_OGRkNN查询方法利用Voronoi图的邻接特性可以在剪枝阶段有效地过滤掉大量的非候选者，快速地缩小查询范围，提高整个算法的查询效率，在精炼阶段有效地提高了算法的准确性.进一步给出了3种情况下的DYN_OGRkNN查询方法，分别为障碍物动态增加情况下的OGRkNN查询算法、障碍物动态减少情况下的OGRkNN查询算法以及障碍物动态移动情况下的OGRkNN查询算法.理论研究和实验结果表明所提算法具有较高效率.

关键词：Voronoi图, 组反k最近邻, 障碍空间, 空间数据库, 动态查询,