Optimal Average Disk-Inspection via Fermat's Principle
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908749169426432 |
|---|---|
| author | Georgiou, Konstantinos |
| author_facet | Georgiou, Konstantinos |
| contents | This work resolves the optimal average-case cost of the Disk-Inspection problem, a variant of Bellman's 1955 lost-in-a-forest problem. In Disk-Inspection, a mobile agent starts at the center of a unit disk and follows a trajectory that inspects perimeter points whenever the disk does not obstruct visibility. The worst-case cost was solved optimally in 1957 by Isbell, but the average-case version remained open, with heuristic upper bounds proposed by Gluss in 1961 and improved only recently.
Our approach applies Fermat's Principle of Least Time to a recently proposed discretization framework, showing that optimal solutions are captured by a one-parameter family of recurrences independent of the discretization size. In the continuum limit these recurrences give rise to a single-parameter optimal control problem, whose trajectories coincide with limiting solutions of the original Disk-Inspection problem. A crucial step is proving that the optimal initial condition generates a trajectory that avoids the unit disk, thereby validating the optics formulation and reducing the many-variable optimization to a rigorous one-parameter problem. In particular, this disproves Gluss's conjecture that optimal trajectories must touch the disk.
Our analysis determines the exact optimal average-case inspection cost, equal to $3.549259\ldots$ and certified to at least six digits of accuracy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_06334 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Average Disk-Inspection via Fermat's Principle Georgiou, Konstantinos Discrete Mathematics This work resolves the optimal average-case cost of the Disk-Inspection problem, a variant of Bellman's 1955 lost-in-a-forest problem. In Disk-Inspection, a mobile agent starts at the center of a unit disk and follows a trajectory that inspects perimeter points whenever the disk does not obstruct visibility. The worst-case cost was solved optimally in 1957 by Isbell, but the average-case version remained open, with heuristic upper bounds proposed by Gluss in 1961 and improved only recently. Our approach applies Fermat's Principle of Least Time to a recently proposed discretization framework, showing that optimal solutions are captured by a one-parameter family of recurrences independent of the discretization size. In the continuum limit these recurrences give rise to a single-parameter optimal control problem, whose trajectories coincide with limiting solutions of the original Disk-Inspection problem. A crucial step is proving that the optimal initial condition generates a trajectory that avoids the unit disk, thereby validating the optics formulation and reducing the many-variable optimization to a rigorous one-parameter problem. In particular, this disproves Gluss's conjecture that optimal trajectories must touch the disk. Our analysis determines the exact optimal average-case inspection cost, equal to $3.549259\ldots$ and certified to at least six digits of accuracy. |
| title | Optimal Average Disk-Inspection via Fermat's Principle |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2509.06334 |