摘要: 将查询点作为Delaunay图的一个生成点,利用Delaunay图的生成点与其邻接生成点之间的关系,在查询点的邻接生成点集(元素个数小于等于6)中计算数据集中给定点的反向最近邻。把伴随Delaunay图增量生成过程产生的Delaunay树作为查询索引结构,该结构能存储Delaunay图,在数据点插入和删除时维护Delaunay图的拓扑结构。
关键词:
反向最近邻,
Delaunay图,
Delaunay树
Abstract: 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 Delaunay incremental generation as the query index structure, which can store Delaunay diagram and maintain Delaunay diagram topology when a point is added or deleted.
Key words:
Reverse Nearest Neighbor(RNN),
Delaunay diagram,
Delaunay tree
中图分类号:
王 淼;郝忠孝;. 基于Delaunay图的反向最近邻查询[J]. 计算机工程, 2010, 36(5): 59-61.
WANG Miao; HAO Zhong-xiao;. Reverse Nearest Neighbor Query Based on Delaunay Diagram[J]. Computer Engineering, 2010, 36(5): 59-61.