2026-09-21T03:27:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25533 2026-09-05T19:19:28Z ddc:004 open_access

Optimal Average Disk-Inspection via Fermat’s Principle Georgiou, Konstantinos Inspection Disk Average-Case Performance 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Konstantinos Georgiou 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.44 urn:nbn:de:0030-drops-255331 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.44 eng https://creativecommons.org/licenses/by/4.0/legalcode