Correctness of Algorithm

This algorithm works by identifying candidate locations for the center. In order for the algorithm to be correct the list of candidates must include the optimal solution. Since it should be trivial to see that if the list of candidates does include the optimal solution, the algorithm is correct, I will concentrate on showing that the list of candidate locations does include the optimal solution.

The proof of correctness depends on two lemmas. The Minimum Width Feasible Annulus Lemma specifies that the minimum width feasible annulus with fixed inner radius must satisfy at least one of the following:

three Points or a Diametral Pair on the Outer Circle;
two Points on the Inner Circle and One on the Outer; or
two Points on the Outer Circle and One Point on the Inner Circle.

This lemma says that if an annulus is minimal width, then it must fall in one of three cases.

The Center Lemma builds on the Minimum Width Feasible Annulus Lemma to identify a list of O(n) candidate center points. The list is comprehensive because the list must contain the optimal solution. For each of the three cases in the Minimum Width Feasible Annulus Lemma there are O(n) candidate center points. Thus combining the candidate center points for each case yields an O(n) comprehensive list of candidate center points.

After having identified O(n) candidate center points, the algorithm checks each one individually. It should be trivial to see that the algorithm must find a minimum width annulus.