首页> 外文会议>WALCOM: algorithms and computation >All Farthest Neighbors in the Presence of Highways and Obstacles
【24h】

All Farthest Neighbors in the Presence of Highways and Obstacles

机译:有公路和障碍物时所有最远的邻居

获取原文
获取原文并翻译 | 示例

摘要

We consider the problem of computing all farthest neighbors (and the diameter) of a given set of n points in the presence of highways and obstacles in the plane. When traveling on the plane, travelers may use highways for faster movement and must avoid all obstacles. We present an efficient solution to this problem based on knowledge from earlier research on shortest path computation. Our algorithms run in O(nm(log m + log~2 n)) time using O(m + n) space, where the m is the combinatorial complexity of the environment consisting of highways and obstacles.
机译:我们考虑在平面中存在高速公路和障碍物的情况下计算给定n点集合的所有最远邻居(和直径)的问题。在飞机上旅行时,旅行者可能会使用高速公路以加快运动速度,并且必须避开所有障碍物。我们基于对最短路径计算的早期研究中的知识,提出了针对此问题的有效解决方案。我们的算法使用O(m + n)空间在O(nm(log m + log〜2 n))时间中运行,其中m是由高速公路和障碍物组成的环境的组合复杂度。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号