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

Reverse Nearest Neighbor Query Based on Delaunay Diagram

将查询点作为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.