首页 | 本学科首页   官方微博 | 高级检索  
     

Voronoi图的生成及近邻关系查询方法
引用本文:张丽平,李松,麻琳,唐远新,郝晓红.Voronoi图的生成及近邻关系查询方法[J].计算机应用,2014,34(12):3470-3474.
作者姓名:张丽平  李松  麻琳  唐远新  郝晓红
作者单位:哈尔滨理工大学 计算机科学与技术学院,哈尔滨 150080
基金项目:黑龙江省教育厅科学技术研究项目
摘    要:针对构建Voronoi图的方法的生成效率较低,构建复杂度较高的问题,提出了利用多方法交叉融合进行Voronoi图的构建与更新的方法。为了提高空间数据最近邻查询的效率,提出了基于Voronoi图和Voronoi多边形最小内切圆的最近邻查询方法;针对查询点位置频繁变化的情况,提出了基于Voronoi图和Voronoi多边形最小外接矩形的最近邻查询方法;为了提高对偶近邻对和最近对的查询效率,利用Voronoi多边形和对应的最小内切圆进行过滤和查询,提出了统一查询对偶近邻对和最近对的新方法。实验结果表明,所提方法解决了因数据分布不均导致的额外计算量的开销问题,在数据集规模较大和查询频率较高时具有一定的优势。

关 键 词:Voronoi图  最近邻  对偶最近邻  最近对  Delannay三角网
收稿时间:2014-06-10
修稿时间:2014-07-30

Methods of Voronoi diagram construction and near neighbor relations query
ZHANG Liping LI Song MA Lin TANG Yuanxin HAO Xiaohong.Methods of Voronoi diagram construction and near neighbor relations query[J].journal of Computer Applications,2014,34(12):3470-3474.
Authors:ZHANG Liping LI Song MA Lin TANG Yuanxin HAO Xiaohong
Affiliation:School of Computer Science and Technology, Harbin University of Science and Technology, Harbin Heilongjiang 150080, China
Abstract:The existing methods of constructing Voronoi diagram have low efficiency and high complexity, to remedy the disadvantages, a new method of constructing and updating Voronoi diagram based on the hybrid methods was given to query the nearest neighbor of the given spatial data effectively, and a new method of searching the nearest neighbor based on Voronoi diagram and the minimum inscribed circle was presented. To deal with the frequent, changes of the query point position, the method based on Voronoi diagram and the minimum bounding rectangle was proposed. To improve the efficiency of the dual nearest neighbor pair and closest pair query, a new method was given based on Voronoi polygons and their minimum inscribed circles. The experimental results show that the proposed methods reduce the additional computation caused by the uneven distribution of data and have a large advantage for the big dataset and the frequent query.
Keywords:
本文献已被 CNKI 等数据库收录!
点击此处可从《计算机应用》浏览原始摘要信息
点击此处可从《计算机应用》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号