Bellman's lost-in-a-forest problem is an unsolved minimization problem in

geometry Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...

, originating in 1955 by the American applied mathematician Richard E. Bellman. The problem is often stated as follows: ''"A hiker is lost in a forest whose shape and dimensions are precisely known to him. What is the best path for him to follow to escape from the forest?"'' It is usually assumed that the hiker does not know the starting point or direction he is facing. The best path is taken to be the one that minimizes the worst-case distance to travel before reaching the edge of the forest. Other variations of the problem have been studied. Although non-contrived real-world applications are not apparent, the problem falls into a class of geometric optimization problems, including search strategies that are of practical importance. A bigger motivation for study has been the connection to

Moser's worm problem Moser's worm problem (also known as mother worm's blanket problem) is an unsolved problem in geometry formulated by the Austrian-Canadian mathematician Leo Moser in 1966. The problem asks for the region of smallest area that can accommodate ever ...

. It was included in a list of 12 problems described by the mathematician Scott W. Williams as "million buck problems" because he believed that the techniques involved in their resolution will be worth at least a million dollars to mathematics.{{Cite journal , last1 = Williams , first1 = S. W., title = Million buck problems , volume = 31 , issue = 2 , year = 2000 , journal = National Association of Mathematicians Newsletter , pages = 1–3 , url = http://www.math.buffalo.edu/~sww/0papers/million.buck.problems.mi.pdf

Known cases

Although it is not known how to find an optimal solution for an arbitrary shape, the optimal solution is known for some special shapes and special classes of shapes: *If the forest contains a 60° rhombus whose long diagonal is a

diameter In geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...

of the forest, then the optimal escape path length is the diameter, and walking in a straight line for this distance will provide an optimal escape. This case includes, for instance, a circular forest. *The optimal escape path for a semicircular forest, or more generally a forest in the shape of a

circular sector A circular sector, also known as circle sector or disk sector or simply a sector (symbol: ⌔), is the portion of a disk (a closed region bounded by a circle) enclosed by two radii and an arc, with the smaller area being known as the ''minor ...

with angle at least 60°, is also the diameter of the forest, as is the optimal escape path for a

regular polygon In Euclidean geometry, a regular polygon is a polygon that is Equiangular polygon, direct equiangular (all angles are equal in measure) and Equilateral polygon, equilateral (all sides have the same length). Regular polygons may be either ''convex ...

with more than three sides. *The optimal escape path for an infinite strip of width

w

is a V-shaped path formed from four straight line segments and two shallow circular arcs, of length approximately

2.2783w

. This same path is also optimal for rectangles of height

w

whose diameter is greater than or equal to the length of this path. For rectangles with a shorter diameter, the optimal escape path length is the diameter. A rectangle whose diameter equals the length of the escape path for a strip of the same height provides an example of a shape with two very different optimal escape paths, the path for the strip and a single line segment of the same length as the diameter.

References

Metric geometry Discrete geometry Unsolved problems in geometry Recreational mathematics