摘要
移动环境下基于Voronoi图的最近邻查询必须要解决随时间不断改变的移动点Voronoi图的拓扑结构的维护问题。通过一组离散的,有限的事件序列对其对偶图Delaunay图拓扑改变过程的模拟来实现对移动点Voronoi图拓扑结构的维护。把带有事件驱动机制的移动数据结构(Kinetic Data Structure,KDS)模型作为移动点的运动模型,给出了KDS模型对其对偶图Delaunay图拓扑结构改变维护的具体策略,并对移动环境下动态插入或删除移动点时Voronoi图的拓扑维护问题进行了研究。最后给出了移动环境下基于Voronoi图的近邻查询的数据库实现模型。
Nearest neighbors inquiry based on Voronoi diagrams must realize maintaining Voronoi diagrams of moving points which changes continuously over time in mobile environment.This paper emploies a collection of discrete and limit topological events which simulates topological changes of Delaunay diagrams,the dual graph of Voronoi diagrams,to realize maintaining Voronoi diagrams of moving points.This paper takes Kinetic Data Structure （KDS） which has an event driven mechanism as mobile modle of moving points,proposes concrete strategies maintaining Delaunay diagrams.The authors also study maintaining Voronoi diagrams of moving points when a point is added or deleted after.At last this paper offers a realization model of nearest neighbors inquiry based on Voronoi diagrams in database.
出处
《计算机工程与应用》
CSCD
北大核心
2008年第31期173-177,共5页
Computer Engineering and Applications
