| 移动点Voronoi图拓扑维护策略的研究 |
| |
| 引用本文： | 王淼,郝忠孝.移动点Voronoi图拓扑维护策略的研究[J].计算机工程与应用,2008,44(31):173-177. |
| |
| 作者姓名： | 王淼 郝忠孝 |
| |
| 作者单位： | 1. 哈尔滨理工大学,计算机科学与技术学院,哈尔滨,150080
2. 哈尔滨理工大学,计算机科学与技术学院,哈尔滨,150080;哈尔滨工业大学,计算机科学与技术学院,哈尔滨,150001 |
| |
| 摘 要： | 移动环境下基于Voronoi图的最近邻查询必须要解决随时间不断改变的移动点Voronoi图的拓扑结构的维护问题。通过一组离散的,有限的事件序列对其对偶图Delaunay图拓扑改变过程的模拟来实现对移动点Voronoi图拓扑结构的维护。把带有事件驱动机制的移动数据结构(Kinetic Data Structure,KDS)模型作为移动点的运动模型,给出了KDS模型对其对偶图Delaunay图拓扑结构改变维护的具体策略,并对移动环境下动态插入或删除移动点时Voronoi图的拓扑维护问题进行了研究。最后给出了移动环境下基于Voronoi图的近邻查询的数据库实现模型。
|
| 关 键 词： | Voronoi图 Delaunay图 移动数据结构 |
| 收稿时间： | 2007-12-10 |
| 修稿时间： | 2008-4-7
|
Research on strategies of maintaining Voronoi diagrams of moving points |
| |
| WANG Miao,HAO Zhong-xiao.Research on strategies of maintaining Voronoi diagrams of moving points[J].Computer Engineering and Applications,2008,44(31):173-177. |
| |
| Authors: | WANG Miao HAO Zhong-xiao |
| |
| Affiliation: | 1.College of Computer Science and Technology，Harbin University of Science and Technology，Harbin 150080，China 2.College of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001，China |
| |
| Abstract: | 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 |
| |
| Keywords: | Voronoi diagrams Delaunay diagrams Kinetic Data Structure(KDS) |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
