关键词: Voronoi图, 反向最近邻, 查询算法

Abstract: Based on the inherent properties and structural characteristics of Voronoi diagrams, this paper conducts an in-depth study on the reverse nearest neighbors query problem to identify and correct theoretical omissions and errors in the existing literature. By deriving relevant theorems and presenting strict proofs, the authors propose a novel method for dynamically updating reverse nearest neighbors when generating points are inserted or deleted that can effectively reduce the retrieval scope of query and update. Moreover, three algorithms named VRNNQ, VRNN_Add and VRNN_Del are designed for reverse nearest neighbors query and dynamic update, all of which achieve a time complexity of O（logn）. Experimental results verify that the proposed algorithms possess remarkable advantages in time execution efficiency.

Key words: Voronoi diagram, reverse nearest neighbor, query algorithm