More than fifty years ago, Bellman asked for the best escape path within a known forest but for an unknown starting position. This deterministic finite path is the shortest path that leads out of a given environment from any starting point. There are some worst case positions where the full path length is required. Up to now such a fixed ultimate optimal escape path for a known shape for any starting position is only known for some special convex shapes (i.e., circles, strips of a given width, fat convex bodies, some isosceles triangles). Therefore, we introduce a different, simple and intuitive escape path, the so-called certificate path. This escape path depends on the starting position s and takes the distances from s to the outer boundary of the environment into account. Due to the additional information, the certificate path always (for any position s) leaves the environment earlier than the ultimate escape path, in the above convex examples. Next we assume that fewer information is available. Neither the precise shape of the envir- onment, nor the location of the starting point is known. For a class of environments (convex shapes and shapes with kernel positions), we design an online strategy that always leaves the environment. We show that the path length for leaving the environment is always shorter than 3.318764 the length of the corresponding certificate path. We also give a lower bound of 3.313126, which shows that for the above class of environments the factor 3.318764 is (almost) tight.
For circles and fat convex bodies, it was shown that the diameter is the ultimate optimal escape path; see Finch and Wetzel @cite_2 . For the infinite strip of width @math , the ultimate optimal escape path is due to Zalgaller @cite_24 @cite_0 . For the simple equilateral triangle of side length @math , the zig-zag path of Besicovitch @cite_22 of length @math is optimal; see also @cite_19 . Furthermore, in 1961 Gluss @cite_5 introduced the problem of searching for a circle @math of given radius @math and given distance @math away from the start @math . Two different cases can be considered, either @math is inside @math or not. Interestingly, in the latter case and for @math a certificate path with length @math and an arc of length @math is the best one can do.
@cite_22 @cite_24 @cite_19 @cite_0 @cite_2 @cite_5
30004998 2167932946 1966842210 2070044474 2094588925
A long standing conjecture is that the Besicovitch triangle, i.e., an equilateral triangle with side ( 28 27 , ) is a worm-cover. We will show that indeed there exists a class of isosceles triangles, that includes the above equilateral triangle, where each triangle from the class is a worm-cover. These triangles are defined so that the shortest symmetric z-arc stretched from side to side and touching the base would have length one. From a random point O in an infinite strip of width 1, we move in a randomly chosen direction along a curve Г. What shape of Г gives the minimum value to the expectation of the length of the path that reaches the boundary of the strip? After certain arguments suggesting that the desired curve belongs to one of four classes, it is proved that the best curve in those classes consists of four parts: an interval OA of length a, its smooth continuation, an arc AB of radius 1 and small length φ, an interval BD that is smooth continuation of the arc, and an interval DF (with a corner at the point D). If O is the origin and OA is the x axis of a coordinate system, then the coordinates of the above-mentioned points are as follows: A(a, 0), B(a + sin φ, 1 − cos φ), F(a, 1), and @math For the best curve, we have: a ≈ 0.814 and φ ≈ 0.032. Related questions are discussed. Bibliography: 9 titles. Call a path an escape path if it eventually leads out of the forest no matter what the initial starting point or the relative orientations of the path and forest. To solve the "lost in a forest" problem we must find the "best" escape path. Bellman proposed two different interpretations of "best," one in which the maximum time to escape is minimized, and one in which the expected time to escape is minimized. A third interpretation (see The problem has been considered by Isbell of determining the path that minimizes the maximum distance along the path to a line in the same plane whose distance from the starting point of the search is known, while its direction is unknown. We consider in this article the analogous problem for the search for a circle of known radius, of known distance from a starting point in its plane. It is further shown that Isbell's solution is a limiting case of the problem posed as the radius of the circle tends to infinity. The problem appears to be of some practical significance, since it is equivalent to that of searching for an object a given distance away which will be spotted when we get sufficiently close—that is, within a specific radius.