基于Delaunay图的反向最近邻查询  

Reverse Nearest Neighbor Query Based on Delaunay Diagram

作　　者：王淼[1] 郝忠孝[1,2] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080 [2]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机工程》2010年第5期59-61,共3页Computer Engineering

基　　金：黑龙江省自然科学基金资助项目(F2006-01)

摘　　要：将查询点作为Delaunay图的一个生成点,利用Delaunay图的生成点与其邻接生成点之间的关系,在查询点的邻接生成点集(元素个数小于等于6)中计算数据集中给定点的反向最近邻。把伴随Delaunay图增量生成过程产生的Delaunay树作为查询索引结构,该结构能存储Delaunay图,在数据点插入和删除时维护Delaunay图的拓扑结构。This paper takes query point as a generation point of Delaunay diagram and utilizes the relationship between this point and its adjacent generation point to search Reverse Nearest Neighbor（RNN） in adjacent generation point set（less than six elements） of query point. It takes Delaunay tree generated during the process of De^aunay incremental generation as the query index structure, which can store Delaunay diagram and maintain Delaunay diagram topology when a point is added or deleted.

关 键 词：反向最近邻 Delaunay图 Delaunay树 

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