Imagine being lost in a forest. You do not know where you are or what direction you are facing, but you do know the exact shape and size of the forest. What is the best path to take to ensure the lowest escape time in the worst case scenario?
An Unsolved Problem
There is no known general solution to this problem. Such a solution would be some kind of algorithm where you plug in the forest’s shape and size and it gives you back the best path of escape. However, some specific cases have been proven.
Fat Forests
One possibility is that a forest is “fat,” meaning that the best escape route is simply a linear path. Just walk in a straight line. For instance, every regular polygon with at least four sides is fat. The only regular polygon with no known solution is the equilateral triangle.
Why Is This So Hard?
The problem was posed by Richard Bellman in 1956, and it remains open for most forest shapes. What makes it so difficult is that the lost person has zero information about their position or orientation. The escape path has to work for every possible starting point and every possible direction, which turns a seemingly simple geometry question into a minimax optimization problem over an infinite number of scenarios. Even for shapes as basic as an equilateral triangle, no one has been able to determine the shortest curve that guarantees escape from every possible starting configuration.
Leave a Reply