Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. The previous best algorithm was given by Hershberger and Suri [FOCS 1993, SIAM J. Comput. 1999] and the algorithm runs in $O(n\log n)$ time and $O(n\log n)$ space, where $n$ is the total number of vertices of all obstacles. The algorithm is time-optimal because $\Omega(n\log n)$ is a lower bound. It has been an open problem for over two decades whether the space can be reduced to $O(n)$. In this paper, we settle it by solving the problem in $O(n\log n)$ time and $O(n)$ space, which is optimal in both time and space; we achieve this by modifying the algorithm of Hershberger and Suri. Like their original algorithm, our new algorithm can build a shortest path map for a source point $s$ in $O(n\log n)$ time and $O(n)$ space, such that given any query point $t$, the length of a shortest path from $s$ to $t$ can be computed in $O(\log n)$ time and a shortest path can be produced in additional time linear in the number of edges of the path.


翻译:鉴于飞机上的一系列双向脱节多边形障碍,在两个点之间找到一个避免障碍的欧几里德最短路径,这是计算几何学上的一个典型问题,而且已经广泛研究了。以前的最佳算法是赫什伯格和苏里[FOCS,1993年,SIAM J.Comput. 1999]给出的。算法以美元(n)美元和美元(n)美元(n)美元)时间和美元(n)空间运行,其中美元是所有障碍的总数。算法是时间-最理想的,因为美元(n)在计算几点之间是一个典型的问题。在过去20多年里,这个算法是赫什贝杰和苏里给出的最好的算法是:用美元(n)美元(n)时间和美元(n)空间,这在时间和空间上都是最优的。我们的新算法可以用美元(n)美元(n)在任何源的轨道上绘制一个最短的路径图,用美元($($),在美元(n)的轨道上,用美元(n)任何源点可以用美元(n)计算出一个最短的路径。

0
下载
关闭预览

相关内容

专知会员服务
39+阅读 · 2020年9月6日
【ST2020硬核课】深度学习即统计学习,50页ppt
专知会员服务
65+阅读 · 2020年8月17日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
用霍夫变换&SCNN码一个车道追踪器
全球人工智能
4+阅读 · 2019年2月10日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
carla 学习笔记
CreateAMind
9+阅读 · 2018年2月7日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2020年12月4日
VIP会员
相关VIP内容
专知会员服务
39+阅读 · 2020年9月6日
【ST2020硬核课】深度学习即统计学习,50页ppt
专知会员服务
65+阅读 · 2020年8月17日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
用霍夫变换&SCNN码一个车道追踪器
全球人工智能
4+阅读 · 2019年2月10日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
carla 学习笔记
CreateAMind
9+阅读 · 2018年2月7日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员