基于Voronoi图的线段最近对查询

摘要：

最近对查询是空间数据库中的重要查询之一.已有的关于最近对查询的研究基本集中在点对象上,对空间对象无法抽象为点的对象则研究较少.提出基于平面线段的最近对查询,即找出两个平面线段集中距离最近的线段对.提出基于Voronoi图的线段最近对查询算法,该方法构造两个线段集的Voronoi图,利用Voronoi图的最近邻近特性和局域动态特性找到互为最近邻的线段对,从中找到结果,以缩减大量的计算代价.对线段集中增加线段和删除线段的情况做了相应的处理.实验证明,该算法具有较高的查询效率.

关键词：线段Voronoi图、空间数据库、线段最近对、线段最小距离

所属期刊栏目：39

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

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

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

页数：共4页

页码：143-146