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

作者：张丽平; 经海东; 李松; 崔环宇

来源：计算机科学, 2016, 43(05): 174-187.

• Voronoi图
• k最近邻查询(kNN)
• 障碍空间
• 障碍距离

为了提升障碍空间中k最近邻查询的效率,研究了障碍空间中基于Voronoi图的k最近邻查询方法,提出了在障碍空间基于Voronoi图的kNN-Obs算法。该算法采用了两个过程:过滤过程和精炼过程。过滤过程主要是利用Voronoi图的过滤功能,较大程度地减少了被查询点的个数。精炼过程主要根据障碍距离和邻接生成点对候选集内对象进行第二次筛选。进一步给出了处理新增加点的ADDkNN-Obs算法和处理删除点的DENkNN-Obs算法。实验表明该算法在处理障碍空间中的k最近邻问题时具有优势。

• 出版日期2016
• 单位哈尔滨理工大学