基于Voronoi图的线段最近对查询 (2012年)

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