Optimal Average Disk-Inspection
via Fermat’s Principle

We begin by defining inspective trajectories and formalizing both the worst-case and average-case versions of Disk-Inspection, leading up to the main theorem.

The requirement that the curve segment be piecewise differentiable stems from the fact that the problem we study concerns arc lengths. This leads to the following problem, also known as the shoreline problem with known distance.

The Worst-Case Disk-Inspection problem was solved in [31], with optimal cost $1+\sqrt{3}+7\pi /6\approx 6.39724$. Inspective trajectories admit two equivalent descriptions, see [16]. First, they inspect every point of the unit disk in the following sense. For any perimeter point $P$ there exists a point $A$ on the trajectory such that $\Vert \lambda A+(1-\lambda )P\Vert \ge 1$ for all $\lambda \in [0,1]$ (that is, $A$ sees $P$ without obstruction by the disk). Second, the trajectories intersect every line tangent to the unit disk (i.e. they discover eventually all shorelines). In what follows we use the inspection perspective, which will also define the average-case problem.

Given an inspective trajectory and a point $P$ on the unit disk, define the inspection time $I_P$ as the length of the trajectory from the origin to the first point that inspects $P$ (equivalently, the time for a unit-speed inspector starting at the origin to see $P$ from outside the disk). The Worst-Case Disk-Inspection, i.e. Problem 2, asks for the inspective trajectory that minimizes ${sup}_P{I}_P$, where the supremum is over all perimeter points $P$. The average-case version replaces the supremum by expectation.

The cost of ADI is defined with respect to an inspector starting at the disk’s center and following an inspective trajectory. One may also allow randomized algorithms that draw a curve from a distribution of inspective trajectories. After the algorithm is fixed, the adversary selects a point $P$, and the algorithm’s performance is the expected inspection time at $P$. If the algorithm first applies a uniform random rotation, then all perimeter points are symmetric, and the adversary’s choice of $P$ has no effect. In this case the cost of a distribution equals the expected inspection time of a randomly chosen point, which is minimized by the deterministic curve achieving the smallest such expectation. Thus the deterministic ADI problem already captures the randomized model.

The average-case problem was first studied by Gluss [29], who proposed two heuristic strategies and conjectured that optimal trajectories touch the disk. More recently, a discretization-based nonlinear programming framework was developed [15, 16], yielding the first systematic upper bounds, with best reported value $3.5509015$. However, the nonconvexity of this approach precluded global optimality guarantees, and no lower bounds were known, so the exact optimum remained unresolved. We resolve this problem with the following result, establishing the optimal value of ADI with high numerical accuracy. In particular, we prove that the previously reported upper bound in [16] was indeed very close to optimal, and we obtain this conclusion through a new continuous framework that replaces the earlier discrete, upper-bound approach. The technical contributions underlying this framework are presented in Section 2.2. We now state our main result.

All numerical errors are controlled as in Section 5.3, yielding at least six correct decimal digits, with a discussion on numerical robustness in Section 5.4. The trajectory certifying Theorem 4 is shown in Figure 1 and quantified in the next section.

Our second contribution is a continuous framework that replaces the discrete approach of [16]. In this framework, candidate inspection trajectories are described, partially, by trajectories generated from an ordinary differential equation (ODE) system. The system is governed by a single real parameter, which turns ADI into a one-parameter optimal control problem. We now introduce the ODE system and the associated trajectories, which form the basis of the technical result leading to Theorem 4.

It can be shown that $\text{Sys}({\tau }_0)$ is well defined near $x=0$ and extends uniquely to $[0,1]$. We later solve this system numerically to identify the trajectories defined below.

We refer to ${𝒯}^{{\tau }_0}$, the solution to ODE $\text{Sys}({\tau }_0)$, as a curve. For suitable ${\tau }_0>0$, this curve corresponds to a portion of the optimal inspective trajectory certifying Theorem 4. Not every choice of ${\tau }_0$ yields an inspective trajectory, which is why in the following definition we distinguish some ${\tau }_0$ that result to curves that do not intersect the unit disk.

Following the standard shoreline framework (see, e.g., [16], building on [29]), we restrict attention to ADI trajectories that start with a a so-called deployment phase. This is defined as a line segment connecting the center of the disk to some point $A_{\mathrm{\infty }}$ on the line $x=1$, where the slope $\theta$ of segment $O{A}_{\mathrm{\infty }}$ will be referred to as the deployment angle, and hence $A_{\mathrm{\infty }}=(1,\tan \theta )$ with $\theta \in [0,\pi /2)$. The reader may consult Figure 1 which shows the optimal inspective trajectory certifying Theorem 4. The initial deployment phase is followed by the so-called inspection phase shown as the green curve whose other endpoint is $A_0$. In the discrete setting (Figure 3), the endpoint is denoted $A_k$, where $k$ is proportional to a discretization parameter that tends to infinity. It is therefore natural to denote the limiting endpoint by $A_{\mathrm{\infty }}$.

We are now ready to state the main technical result, which expresses the cost of ADI as a function of the curve ${𝒯}^{{\tau }_0}$ and of $(\psi ,\tau )$, the solution to $\text{Sys}({\tau }_0)$. For ease of reference, and inspired by standard terminology in control theory, we call the resulting optimization problem a Single-Parameter Optimal Control Problem (SPOCP) where each feasible solution is the trajectory of an ODE system determined by a single initial condition serving as the decision variable. In our setting the initial parameter is ${\tau }_0$, and the corresponding feasible trajectories are generated by $\text{Sys}({\tau }_0)$. We refer to this problem as $\text{SPOCP}({\tau }_0)$, and is formally stated in Theorem 8 below.

We prove Theorem 8 in Section 5.1. In Section 5.3 we show that the inspection phase of the optimal inspective trajectories do not touch the unit disk. This allows us to invoke Theorem 8 and optimize (1), thereby solving the underlying one-parameter optimal control problem and establishing Theorem 4.

It is convenient to host our arguments on the Cartesian plane and require that the inspecting curves have one endpoint at the origin, where the disk to be inspected is also centered. More specifically, we parameterize the unit disk perimeter by points

where $\varphi \in [0,2\pi )$. Therefore, the subject inspective trajectories are functions $T:[0,1]\to {ℝ}^2$, with $T(0)=(0,0)$. Towards defining the discretized ADI, we first need to introduce a useful partial inspection variant to the problem.

The motivation for introducing $\theta$-inspective curves is that inspection may begin not from the disk center but from a point located at distance $1/\cos \left(\theta \right)$ from it. We reserve the term trajectory for full solutions to ADI, while curve refers to this partial variant. Placing the disk at the origin, we may assume that the starting point is $(1,\tan \left(\theta \right))$, which already inspects all boundary points $P_{\varphi }$ with $\varphi \in [0,2\theta ]$ at zero cost. An example is illustrated in Figure 1, where the $\theta$-inspective curve has endpoints $A_{\mathrm{\infty }}=(1,\tan \left(\theta \right))$ and $A_0$ on the line $x=1$.

Any $\theta$-inspective curve can be extended to an inspective trajectory by appending the line segment from the origin to $(1,\tan \left(\theta \right))$ (previously referred to as the deployment phase). One of the results in [16] was the following explicit relation between the two problems.

In this expression, the logarithmic term accounts for the average cost of inspecting $P_{\varphi }$ with $\varphi \in [0,2\theta ]$ during the initial deployment segment, while the remainder reflects the contribution of the $\theta$-inspective curve. Thus, for each fixed $\theta$, the best partial cost $s_0(\theta )$ yields a full trajectory of cost $B_{\theta }(s_0)$. It follows that the optimal solution to ADI is given by

The task is therefore reduced to selecting the deployment angle $\theta$ and designing the corresponding $\theta$-inspective curve of minimal average cost $s_0(\theta )$. The starting point for our work is the formulation that lead to the upper bound on $B_{\theta }(s_0)$ established in [16].

Theorem 11 is the continuous analogue of Lemma 3 in [16], which is stated for a discrete inspection setting. The proof there is geometric and does not rely on discreteness: the total average cost splits into two independent contributions, namely (i) the average cost of inspecting the initial arc of length $2\theta$ during the deployment phase, and (ii) the average cost of inspecting the remaining portion of the perimeter, regardless of whether it consists of finitely many or infinitely many points.

Every feasible ADI trajectory admits such a decomposition. Following the classical shoreline analysis of Isbell and Gluss, one may restrict attention to trajectories whose rim begins with a straight deployment segment from the origin to a point $(1,\tan \theta )$ for some $\theta \in [0,\pi /2)$, and is angularly monotone thereafter. For a fixed $\theta$, the contribution of the continuation to the total ADI cost depends only on the average cost of the corresponding $\theta$-ADI solution. If the continuation were not optimal for that $\theta$-ADI instance, replacing it by a better $\theta$-ADI curve would strictly improve the total ADI cost. Hence, the continuation of any optimal ADI solution must itself be an optimal solution of the associated $\theta$-ADI problem.

We now introduce a discretized version of the partial inspection problem and show how it can be modeled as a nonconvex Nonlinear Program (NLP) with $\mathrm{\Theta }(k)$ variables, yielding a $(1+1/k)$-approximation to the continuous $\theta$-inspection problem.

Fix $\theta \in [0,\pi /2)$ and $k\ge 5$. Define

and let $P_{{\varphi }_i}$ denote the corresponding $k+1$ equidistant points on the arc of the unit circle of length $2\pi -2\theta$, see Figure 3. For convenience, we will abbreviate $P_{{\varphi }_i}$ by $P_i$ when the index meaning is clear from context.

We assume $k\ge 5$ so that the angular spacing between consecutive discretization angles is strictly less than $\pi /2$; this condition is required to ensure that feasibility of the discretized formulation implies feasibility of the corresponding continuous inspection trajectory, as already used in [16].

As $k\to \mathrm{\infty }$, $(\theta ,k)$-inspective curves approximate $\theta$-inspective curves. In particular, scaling a $(\theta ,k)$-inspective curve by a factor $1+O(1/k)$ produces a $\theta$-inspective curve, which is one interpretation of the upper bounds derived in [16].

Let now $L_i(t)$ be the tangent line at $P_i$, parameterized by

Each line $L_i(t)$ passes through $P_i$ at $t=0$ and is tangent to the unit disk. For parameters $t_i\ge 0$, define $A_i:=L_i(t_i)$. In particular, we fix $t_k=\tan \left(\theta \right)$ so that $A_k=(1,\tan \left(\theta \right))$. A candidate $(\theta ,k)$-inspective curve is then the polygonal chain

see Figure 3.

The next lemma expresses the average inspection cost in terms of the parameters $t_i$.

We begin by introducing Snell’s Law, along with terminology that will be used in subsequent sections. The exposition starts with the Principle of Least Time, also known as Fermat’s Principle, which postulates that the trajectory of a light ray between two given points is the one that minimizes travel time. The principle has been confirmed through experimental observation and explains the rules of refraction in ray optics.

Consider two media with constant speeds $s_1,s_2$, separated by a line $\mathrm{\ell }$ with normal $\eta$; see Figure 2. Assume light has constant speed in each medium, hence it travels along a straight ray within each. A ray from $A_1$ to $A_2$ refracts at $L\in \mathrm{\ell }$, forming angles ${\alpha }_1,{\alpha }_2$ with normal $\eta$ and obeying Snell’s Law below. For simplicity, we refer to phase velocity as speed.

Although Snell’s Law is an experimental law of optics, it can be derived rigorously from Fermat’s Principle. We present the formal claim next.

In this section we compute the optimal solution to $(\theta ,k)$-ADI and its cost using recursion derived from the optics principles of the previous section.

Fix $\theta \in [0,\pi /2)$ and $k\in \mathbb{Z}$, see Figure 3. A solution to $(\theta ,k)$-ADI is determined by values $t_i\ge 0$ that specify points $A_i=L_i(t_i)$ on tangent halflines $L_i(t)$, $i=0,\mathrm{\dots },k$, which in turn inspect perimeter points $P_i$. For given $t_i$ we define the following counterclockwise angles:

and distances

Let also denote

that is, $\alpha$ is the angular distance between two consecutive points $P_i,P_{i+1}$ on the perimeter.

We now prove Theorem 8. The starting point is the recurrence of Lemma 17, which describes the optimal inspective curve as an optics trajectory with refraction angles independent of $t_k=\tan \left(\theta \right)$. The deployment angle $\theta$ still determines the trajectory and its cost, and fixes the endpoint $A_0=L_0(t_0)=(1,-t_0)$. Thus the trajectory connecting two points of the line $x=1$ in the first and fourth quadrants (see Figure 3) may be viewed either as a ray starting from $A_k$ in the first quadrant or from $A_0$ in the fourth.

For technical reasons, rather than parameterizing the recurrence by $t_k=\tan \left(\theta \right)$, we work with $t_0={\tau }_0$, restricted to the feasible range of Definition 7. The challenge is then to determine the point where the trajectory intersects the line $x=1$ again, and hence the corresponding deployment angle $\theta$. In Lemma 17 the angular step is $\alpha =2(\pi -\theta )/k$, still vanishing as $k\to \mathrm{\infty }$ but expressed in terms of $\theta$. To eliminate this dependence we place $n$ equispaced points $P_0,\mathrm{\dots },P_n$ on the unit circle, with step $\alpha =2\pi /n$, and recover $\theta$ as a function of ${\tau }_0$.

This setup leads to the following continuum limit as $n\to \mathrm{\infty }$, namely the ODE system $\text{Sys}({\tau }_0)$ of Definition 5. The corresponding trajectory $𝒯$ begins at $(1,-{\tau }_0)$, remains outside the unit disk, and intersects the line $x=1$ in the first quadrant at some point $𝒯(\xi )$, where $\xi$ is the deployment parameter. We now state a sequence of technical results establishing this limit.

First, we show that if the discrete recursion is extended to continuous functions by connecting consecutive values linearly, the resulting piecewise-linear functions converge to the solution of the ODE system $\text{Sys}({\tau }_0)$ of Definition 5.

We are now ready to provide the limiting behavior of the inspecting curve, giving rise to ${𝒯}^{{\tau }_0}$ as in Definition 6. In the remainder of the section, for notational convenience, we drop the superscript and write simply $𝒯$. The next lemma shows that the polygonal trajectories converge indeed to $𝒯$.

Since $𝒯$ arises as the continuum limit of the discrete trajectories, the endpoint $A_k$ of the polygonal path (see Figure 3) corresponds to an index $k=\mathrm{\Theta }(n)$. As $n\to \mathrm{\infty }$ this endpoint is denoted $A_{\mathrm{\infty }}$ in Figure 1. We can now justify the definition of the deployment parameter.

From the progress above, and starting with inspection-feasible ${\tau }_0$, we compute $\theta$-inspective curve to $\theta$-ADI, where $\theta =\theta (\xi )$, and $\xi =\xi ({\tau }_0)$. The next lemma uses again the continuum construction to derive the cost of $𝒯$ to $\theta$-ADI, as a function of ${\tau }_0$, and in terms of the solution to ODE system $\text{Sys}({\tau }_0)$.

We can now conclude the proof of Theorem 8. By (3) and the discussion of Section 3.1, the optimal inspective curve has cost ${inf}_{\theta \in [0,\pi /2)}{B}_{\theta }(s_0)$, where $s_0=s_0(\theta )$ is the cost to some $\theta$-ADI instance. Since the optimal curve does not touch the disk, the deployment angle is $\theta =(1-\xi )\pi$ for some inspection-feasible ${\tau }_0$. Lemma 21 gives $s_0$ as a function of $\xi$, which can then be substituted into Theorem 11 to yield the expression of Theorem 8.

Finally, since $\theta \in [0,\pi /2)$ we have $\xi >1/2$, ensuring that expression (1) is well defined. To conclude, it remains to show that the expression attains a minimum, which follows from continuity together with the Extreme Value Theorem.

In light of Theorem 8 proved in the previous section, the natural approach to finding the optimal solution to ADI is to solve the underlying single-parameter (here ${\tau }_0$) optimal control problem with objective (1). Put differently, we are back to determining the optimal solution as ${inf}_{\theta \in [0,\pi /2)}{B}_{\theta }(s_0)$, where $s_0=s_0(\theta )$ is the optimal solution to $\theta$-ADI, see (3). However, not all deployment angles $\theta$ give rise to optimal trajectories that avoid intersecting the disk, which is a premise of Theorem 8.

For this reason, we restrict the range $[0,\pi /2)$ of deployment angles. Small values of $\theta$ are excluded because the corresponding optimal trajectories touch the disk. Large values of $\theta$ are excluded for a different reason: as $\theta \to \pi /2$, the deployment point moves arbitrarily far from the origin, and we show in the next section that such angles cannot be optimal. Consequently, these angles need not be considered in the optimization. We then search numerically for the minimizing deployment angle over the remaining range. Restricting to this range also avoids numerical instability in the associated SPOCP, which would otherwise arise from the large scales involved. The numerical procedures used in this restricted regime are justified in Section 5.4.

To summarize, in this section we show a refinement of (3), as follows.

We start by showing that the deployment angle cannot be too large.

Then, we need a lower bound to the optimal solution to $\theta$-ADI.

We are ready to show that the deployment angle cannot be too small.

Note that Lemma 23 is directly implied by Lemmata 24 and 26.

In this section, we show that the premise of Theorem 8 is satisfied, namely that the optimal inspective curve does not touch the unit disk. Consequently, this allows us to optimize expression (1) and thus conclude with the proof of Theorem 4. We rely on the theoretical foundations established previously, and, as is necessary, we make use of further numerical calculations implemented in the Julia programming language [11]. Many of the arguments below are based on numerical comparisons. In Section 5.4 we provide the justifications that these computations are robust and consistent with the accuracy promised in the main theorem.

The next lemma analyzes inspection trajectories in a carefully chosen regime of initial values ${\tau }_0$ to the ODE system $\text{Sys}({\tau }_0)$.

We used the Julia programming language [11] for all computations.

For the convex nonlinear program that lower bounds $s(\theta )$ in Lemma 26, we model it with JuMP [19] and solve it using the interior point method Ipopt [14, 42]. The program is convex since the feasible set $\{t_i\ge 0\}$ is convex and the objective is a nonnegative conical combination of norms of affine maps. Hence any KKT point is globally optimal. In practice, the solver returns primal and dual feasible solutions with residuals below ${10}^{-14}$ and objective values stable to at least ${10}^{-9}$. Because convexity guarantees global optimality, these certificates validate the solutions and support the digits reported in our lower bounds.

For the ODE system of Definition 5, used in Section 5.3 to establish feasibility of trajectories and to evaluate the cost functional, we proceed as follows. The equation for $\psi$ has a singularity at $x=0$, so we begin the integration at $x_0={10}^{-6}$ using the asymptotic expansion $\psi (x_0)=\pi /2-\pi x_0+({\pi }^2/2)x_0^2$, whose truncation error is $O(x_0^3)\approx {10}^{-18}$ and therefore negligible compared with the solver tolerances. We integrate $\psi$ on $[x_0,1]$ with the adaptive stiff solver Rodas5() from the DifferentialEquations.jl library [41], setting absolute and relative tolerances to ${10}^{-12}$, and then integrate $\tau$ on the same interval using the dense output of $\psi$ in the right-hand side.

The deployment parameter $\xi$ is obtained in two stages. A uniform grid of $10,000$ points provides a coarse ${\xi }_{\text{approx}}$ as the last feasible point according to a geometric predicate that tolerates floating-point noise at the level ${10}^{-12}$. This value is refined by bisection to absolute tolerance ${10}^{-8}$. To further confirm stability, we repeat the bisection at tolerance $5\cdot {10}^{-10}$ and recompute the objective, reporting the discrepancy between the two runs, which is consistently negligible. In addition, the minimum of $\tau (\cdot )$ on $[x_0,{\xi }_{\text{approx}}]$ is computed by Brent’s method [13] with tolerance ${10}^{-10}$ to certify that all trajectories remain uniformly outside the disk.

The integral of Lemma 21 is evaluated using the adaptive Gauss-Kronrod quadrature routine quadgk from QuadGK.jl [33], with relative tolerance ${10}^{-12}$ and absolute tolerance ${10}^{-14}$. Substituting $(\xi ,\theta )$ into the expression of Theorem 8 then yields the values reported in Section 5.3.

Each source of numerical error is explicitly controlled. The asymptotic initialization at $x_0={10}^{-6}$ contributes error below ${10}^{-18}$. The ODE solver controls local error to ${10}^{-12}$. The quadrature routine bounds the relative error for computing integral of Lemma 21 to ${10}^{-12}$. The binary search tolerance ${10}^{-8}$ induces uncertainty on $\theta$ of at most $\pi \cdot {10}^{-8}$, with an even tighter self-check available. Finally, the Brent minimization shows that $\tau (x)\ge 0.2$ throughout, implying $\Vert 𝒯(x)\Vert \ge 1.0198$, so the curves remain at least ${10}^{-2}$ outside the disk. These guarantees confirm that the cost values reported in Theorem 4 are reliable to at least six decimal digits.