“狗咬邮递员”查询研究

"狗咬邮递员"查询是移动点最近邻查询问题的派生问题,是要找到当狗和邮递员以某种恒定速度运动时狗能最快到达的邮递员集合。与一般的移动点最近邻查询不同,"狗咬邮递员"查询中,移动点以恒定速度运动。针对"狗咬邮递员"问题的特殊性,提出在Voronoi图基础上引入三维坐标系并构建移动Voronoi图,利用反向最近邻查询思想,通过检验内部区域和外部区域是否被破坏从而确定查询点能最快到达的点是否因为点的移动而发生改变,最终找到每一时刻移动查询点所能最快到达的点。