Reverse Nearest Neighbor Query Based on Delaunay Diagram
Miao Wang, Hao Zhong-xiao · Jisuanji gongcheng · 2010
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.