Voronoi图的生成及近邻关系查询方法

摘要：

针对构建Voronoi图的方法的生成效率较低,构建复杂度较高的问题,提出了利用多方法交叉融合进行Voronoi图的构建与更新的方法.为了提高空间数据最近邻查询的效率,提出了基于Voronoi图和Voronoi多边形最小内切圆的最近邻查询方法;针对查询点位置频繁变化的情况,提出了基于Voronoi图和Voronoi多边形最小外接矩形的最近邻查询方法;为了提高对偶近邻对和最近对的查询效率,利用Voronoi多边形和对应的最小内切圆进行过滤和查询,提出了统一查询对偶近邻对和最近对的新方法.实验结果表明,所提方法解决了因数据分布不均导致的额外计算量的开销问题,在数据集规模较大和查询频率较高时具有一定的优势.

关键词：Voronoi图、最近邻、对偶最近邻、最近对、Delannay三角网

所属期刊栏目：34

分类号：TP311.13(计算技术、计算机技术)

资助基金：黑龙江省教育厅科学技术研究项目12541122

在线出版日期：2015-02-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：3470-3474