“狗咬邮递员”查询研究  

Research of Dog Bites Postman Query

作　　者：朱婧[1] 

机构地区：[1]齐齐哈尔大学理学院,黑龙江齐齐哈尔161006

出　　处：《科技通报》2012年第3期130-133,共4页Bulletin of Science and Technology

基　　金：黑龙江省教育厅科学技术研究项目(12511610);齐齐哈尔大学青年教师科研启动项目(2010K-M32)

摘　　要："狗咬邮递员"查询是移动点最近邻查询问题的派生问题,是要找到当狗和邮递员以某种恒定速度运动时狗能最快到达的邮递员集合。与一般的移动点最近邻查询不同,"狗咬邮递员"查询中,移动点以恒定速度运动。针对"狗咬邮递员"问题的特殊性,提出在Voronoi图基础上引入三维坐标系并构建移动Voronoi图,利用反向最近邻查询思想,通过检验内部区域和外部区域是否被破坏从而确定查询点能最快到达的点是否因为点的移动而发生改变,最终找到每一时刻移动查询点所能最快到达的点。＂Dog bites postman＂ is the variant of the nearest neighbor of the moving points. The answer is to find the postman that a dog can reach fast when the dog moves with the constant speed. It is different from the general nearest neighbor query of the moving points. In ＂Dog bites postman＂, the query point is moving with the constant speed. To solve the problem,introduce the three-dimensional coordinate and construct the moving Voronoi diagram based on the Voronoi diagram. Then obtain if the point that the query point can reach fast is changed by examining if the interior region and exterior region are broken, which using the thought of reverse nearest neighbor query.

关 键 词：反向最近邻查询 “狗咬邮递员”查询 移动查询点 移动Voronoi图 内部三角形 外部三角形 

分 类 号：TP202.7[自动化与计算机技术—检测技术与自动化装置]