×

On the approximation of shortest escape paths. (English) Zbl 1468.68266

Summary: 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.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
51M16 Inequalities and extremum problems in real or complex geometry
68W25 Approximation algorithms
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bellman, R., Minimization problem, Bull. Am. Math. Soc., 62, 3, 270 (1956)
[2] Williams, S. W., Million-buck problems, Math. Intell., 24, 3, 17-20 (2002)
[3] Finch, S. R.; Wetzel, J. E., Lost in a forest, Am. Math. Mon., 111, 8, 645-654 (2004) · Zbl 1187.51017
[4] Kirkpatrick, D., Hyperbolic dovetailing, (European Symposium on Algorithms (2009), Springer), 516-527 · Zbl 1256.68164
[5] Ogilvy, C. S., Tomorrow’s Math; Unsolved Problems for the Amateur (1972), Oxford University Press · Zbl 0111.00101
[6] Alpern, S.; Gal, S., The Theory of Search Games and Rendezvous, vol. 55 (2006), Springer Science & Business Media
[7] Moser, W. O.J., Problems, problems, problems, Discrete Appl. Math., 31, 2, 201-225 (1991) · Zbl 0817.52002
[8] Zalgaller, V. A., A question of Bellman, J. Math. Sci., 131, 1, 5286-5306 (2005) · Zbl 1211.90271
[9] Adhikari, A.; Pitman, J., The shortest planar arc of width 1, Am. Math. Mon., 96, 4, 309-327 (1989) · Zbl 0692.52001
[10] Chan, T. M.; Golynski, A.; López-Ortiz, A.; Quimper, C., Curves of width one and the river shore problem, (Proceedings of the 15th Canadian Conference on Computational Geometry. Proceedings of the 15th Canadian Conference on Computational Geometry, CCCG’03, Halifax, Canada, August 11-13, 2003 (2003)), 73-75
[11] Klötzler, R., Universale rettungskurven i, Z. Anal. Anwend., 5, 1, 27-38 (1986) · Zbl 0607.49027
[12] Klötzler, R.; Pickenhain, S., Universale rettungskurven ii, Z. Anal. Anwend., 6, 4, 363-369 (1987)
[13] Isbell, J., An optimal search pattern, Nav. Res. Logist. Q., 4, 4, 357-359 (1957)
[14] Sleator, D. D.; Tarjan, R. E., Amortized efficiency of list update and paging rules, Commun. ACM, 28, 2, 202-208 (1985)
[15] (Fiat, A.; Woeginger, G. J., Online Algorithms, The State of the Art (the Book Grow Out of a Dagstuhl Seminar, June, 1996). Online Algorithms, The State of the Art (the Book Grow Out of a Dagstuhl Seminar, June, 1996), Lecture Notes in Computer Science, vol. 1442 (1998), Springer)
[16] Icking, C.; Kamphans, T.; Klein, R.; Langetepe, E., On the competitive complexity of navigation tasks, (Sensor Based Intelligent Robots (2002), Springer), 245-258 · Zbl 1053.68847
[17] Rao, N. S.; Kareti, S.; Shi, W.; Iyengar, S. S., Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms (1993), Oak Ridge National Lab., TN: Oak Ridge National Lab., TN United States, Tech. Rep
[18] Baezayates, R. A.; Culberson, J. C.; Rawlins, G. J., Searching in the plane, Inf. Comput., 106, 2, 234-252 (1993) · Zbl 0781.68044
[19] Fleischer, R.; Kamphans, T.; Klein, R.; Langetepe, E.; Trippen, G., Competitive online approximation of the optimal search ratio, SIAM J. Comput., 38, 3, 881-898 (2008) · Zbl 1187.68259
[20] Koutsoupias, E.; Papadimitriou, C.; Yannakakis, M., Searching a fixed graph, (International Colloquium on Automata, Languages, and Programming (1996), Springer), 280-289 · Zbl 1045.90532
[21] Poole, G.; Gerriets, J., Minimum covers for arcs of constant length, Bull. Am. Math. Soc., 79, 2, 462-463 (1973) · Zbl 0256.52014
[22] Besicovitch, A., On arcs that cannot be covered by an open equilateral triangle of side 1, Math. Gaz., 49, 369, 286-288 (1965) · Zbl 0134.40604
[23] Coulton, P.; Movshovich, Y., Besicovitch triangles cover unit arcs, Geom. Dedic., 123, 1, 79-88 (2006) · Zbl 1119.52010
[24] Finch, S. R.; Zhu, L.-Y., Searching for a shoreline, arXiv preprint (2005)
[25] Eubeler, A.; Fleischer, R.; Kamphans, T.; Klein, R.; Langetepe, E.; Trippen, G., Competitive online searching for a ray in the plane, (Dagstuhl Seminar Proceedings (2007), Schloss Dagstuhl-Leibniz-Zentrum für Informatik)
[26] Finch, S. R., The logarithmic spiral conjecture (2016), preprint
[27] Langetepe, E., On the optimality of spiral search, (Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (2010), SIAM), 1-12 · Zbl 1288.68229
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.