基于Voronoi图及其对偶图的反最近邻查询  

Reverse nearest neighbor query based on Voronoi diagram and delaunay graph

作　　者：张佳佳[1,2] 刘润涛[1,2] 李杨[1,2] 

机构地区：[1]哈尔滨理工大学应用科学学院,哈尔滨150080 [2]哈尔滨理工大学信息与计算科学研究所,哈尔滨150080

出　　处：《计算机工程与应用》2009年第18期162-163,211,共3页Computer Engineering and Applications

基　　金：国家自然科学基金No.10571037;黑龙江省教育厅资助项目No.11511027~~

摘　　要：最近邻查询是地理信息系统领域经常遇到的问题,而反最近邻查询是在最近邻查询的基础上提出的一种新的查询类型。在分析利用Voronoi图进行最近邻查询的基础上,提出了基于Voronoi图及其对偶图Delaunay图的反最近邻查询,大大缩小了在海量空间数据库中进行反最近邻查询的查询范围。Nearest neighbor query is very common in geographic information system,and based on it,reverse nearest neighbor query is proposed,On the basis of the nearest neighbor query based on Voronoi diagram,the reverse nearest neighbor query based on Voronoi diagram and Delaunay graph is proposed.And .the range of the reverse nearest neighbor query is reduced in the large spatial data sets in this method.

关 键 词：VORONOI图 最近邻 反最近邻 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]