← All papers
First page of Proof and More Variations of Bellman's Lost-in-a-forest Problem

Proof and More Variations of Bellman's Lost-in-a-forest Problem

Zhipeng Deng

math.OC Jun 12, 2026 · v3
An appendix gives Lean 4/Mathlib proofs of Theorems 1-7, covering the equivalence of the rigid-motion boundary-intersection formulation and related lemmas.
In this paper, based on our previous general formulation and computational solution to Bellman's Lost-in-a-forest Problem, we provide the proof of general solution and obtained more variations and results related to this problem. This paper provides generalized formalized method connecting curve covering, lost-in-the-forest problem, and traveling salesman problem with neighborhoods. We prove the equivalence and convergence. We also provide more results of searching for two lines, connection to Wetzel's unit arc covering problem, variations with closed path, variations in three dimensions, etc. The results include general calculation equations, partial analytical results, and numerical results.

Bellman's lost-in-a-forest problem asks for the shortest path guaranteed to escape a forest of known shape when the hiker's starting position and orientation are unknown. The authors' earlier computational framework reduced it to a traveling salesman problem with neighborhoods (TSPN) but lacked proofs of equivalence and convergence.

The problem is restated as a rigid-motion boundary-intersection problem. Its discretization is shown to reduce to TSPN, and discrete global optima are shown to converge to the continuous optimum. The framework is extended to searching for two lines, a translation-only weak form linked to Wetzel's unit arc covering problem, closed paths, and three dimensions. Theorems 1-7 are formalized in Lean 4 using Mathlib in an appendix.

The paper proves equivalence and convergence and gives numerical path lengths for two-line searches and closed-path variants across many angles. It also compares 1D, 2D and 3D variants, including a reproduced 3D curve whose convex hull contains the unit ball.

Figure 6: Reproduced non-closed curve originating from the origin whose convex hull contains the unit ball.
AngleArc+Tangent2 segments3 segments4 segments
0°1.627821.665091.632241.63224
90°2.413222.121322.121322.12132
180°3.19862-4.347843.59635
Shortest path lengths for searching for two lines at angle β (selected rows)