On the approximation of shortest escape paths
On the approximation of shortest escape paths
复制标题
DOI：
10.1016/j.comgeo.2020.101709
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
David Kübel;E. Langetepe
中科院分区：
文献类型：
--
作者：
David Kübel;E. Langetepe
一个徒步旅行者在一片形状不明的森林里迷路了。为了在合理的时间内逃离森林，徒步旅行者应该遵循什么好的路径？徒步旅行者的困境显然是：是否应该开始探索附近的区域，并逐渐扩大搜索半径？还是应该选择一个方向，然后一直向前跑？我们采用竞争分析，证明了一定的螺旋策略实现了合理的竞争因子的情况下，森林有一个非空的内核，而且，如果徒步旅行者的未知的起始位置位于森林的内核，这种策略是（几乎）最优的w.r.t.竞争因素。作为我们的竞争分析的基础上，我们引入了一个新的措施，这种逃生问题的实例，我们比较几个已知的最短逃生路径的内在复杂性。
A hiker is lost in a forest of unknown shape. What is a good path for the hiker to follow in order to escape from the forest within a reasonable amount of time? The hiker's dilemma clearly is: Should one start exploring the area close-by and expand the search radii gradually? Or should one rather pick some direction and run straight on?We employ a competitive analysis to prove that a certain spiral strategy achieves a reasonable competitive factor for the case where the forest has a non-empty kernel; moreover, if the hiker's unknown starting position lies in the kernel of the forest, this strategy is (almost) optimal w.r.t. the competitive factor. As a basis for our competitive analysis, we introduce a new measure of intrinsic complexity for instances of this escape problem, which we compare to several known shortest escape paths.