| Title: |
Optimal Average Disk-Inspection via Fermat’s Principle |
| Authors: |
Georgiou, Konstantinos |
| Contributors: |
Konstantinos Georgiou |
| Publisher Information: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| Publication Year: |
2026 |
| Collection: |
DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| Subject Terms: |
Inspection; Disk; Average-Case Performance |
| Description: |
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 [Isbell, 1957], but the average-case version remained open, with heuristic upper bounds proposed by Gluss [Gluss, 1961] in 1961 and improved only recently in [Conley and Georgiou, 2025]. Our approach applies Fermat’s Principle of Least Time from optics to the discretization framework of [Conley and Georgiou, 2025], 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 [Gluss, 1961] that optimal trajectories must touch the disk. Our analysis determines the exact optimal average-case inspection cost, equal to 3.549259… and certified to at least six digits of accuracy. |
| Document Type: |
article in journal/newspaper; conference object |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.44 |
| DOI: |
10.4230/LIPIcs.STACS.2026.44 |
| Availability: |
https://doi.org/10.4230/LIPIcs.STACS.2026.44; https://nbn-resolving.org/urn:nbn:de:0030-drops-255331; https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.44 |
| Rights: |
https://creativecommons.org/licenses/by/4.0/legalcode |
| Accession Number: |
edsbas.9A9386DC |
| Database: |
BASE |