The Center Lemma

The Center Lemma (Lemma 6 (page 14) from the reference paper) states that there are O(n) positions where the center of a thinnest feasible annulus with fixed inner radius covering a specified point set (with n points) may be located. Before jumping into the main assertion and proof of the Center Lemma, it is useful to introduce several new concepts: the Farthest Point Voronoi Diagram and the Boundary of the Union of Open Discs.

The Farthest Point Voronoi Diagram

The Farthest Point Voronoi Diagram is a well known geometrical construct. It is defined for a point set. The Farthest Point Voronoi region of a point, s is the set of all points in the plane that are farther away from s than from any other point in the point set. The Farthest Point Voronoi Diagram is the union of the Farthest Point Voronoi regions for the point set. The Farthest Point Voronoi Diagram has
Generators of a Farthest Point Voronoi Edge
As previously mentioned, a Farthest Point Voronoi Edge is simply the boundary between two Farthest Point Voronoi regions. Also recall that each Farthest Point Voronoi region is associated with a point in the point set. Thus a Farthest Point Voronoi Edge is associated with two points in the point set. These two points are called its generator.

Boundary of the Complement of the Union of Open Discs

For a given point set, consider the set of open discs with the defined radius (the radius specified for the inner circle) that are centered on the points in the point set. Clearly the center of the minimum width annulus can not be located in any of these discs. (If it was then it would not cover at least one point.) Thus the center of the minimum width annulus must be located outside the union of all these disks. In this lemma we will show that the center of the minimum width annulus may be located on the boundary of the complement of the union of open discs (with the specified radius and centered on the points in the point set).

Assertion

The center of the thinnest annulus with fixed inner radius (covering a specified point set) must be
  1. at the midpoint of a diametral pair of points;
  2. a vertex of the Farthest Point Voronoi Diagram of the point set;
  3. at the intersection of a Farthest Point Voronoi Edge and the Boundary of the Union of Open Discs; or
  4. a vertex of the Boundary of the Union of Open Discs.

Proof

Recall from the Minimal Width Feasible Annulus Lemma, the mimimum width annulus must meet one of three criteria. These criteria will form three cases. I will prove the Center Lemma individually for each case. The mimimum width annulus must have at least:

Case 1: Three Points or a Diametral Pair on the Outer Circle

Three Points on the Outer Circle

If there are three points on the outer circle then the center must be a vertex of the Farthest Point Voronoi Diagram (satisfying item 2 of the lemma). Figure 1 shows an annulus that is defined by three points on its outer circle. The figure also shows its Farthest Point Voronoi Diagram (in green).

Figure 1: An Annulus Defined By Three Points on the Outer Circle
A Diametral Pair

On the other hand if there is a diametral pair of points on the outer circle then the pair of points must satisfy item 1 of the lemma. Figure 2 shows an annulus that is defined by a diametral pair. The line segment between the diametral pair is shown in green. Clearly this line segment represents the diameter of the circle as well as the point set.

Figure 2: An Annulus Defined By A Diametral Pair

Case 2: Two Points on the Inner Circle and One on the Outer

Clearly the center satisfies item 4. Figure 3 shows an annulus that is defined by two points on the inner circle and one on the outer circle. The two open discs around the two inner circle points are shown in green. It should be clear that the common center must be on the boundary of the green discs.

Figure 3: An Annulus Defined By Two Point on the Inner Circle and One on the Outer Circle

Case 3: Two Points on the Outer Circle and One Point on the Inner Circle

Since the common center is equidistant from the two points on the outer circle, it must lie on a Farthest Point Voronoi Edge. Since there is at least one point on the outer circle, the common center lies on the Boundary of the Complement of the Union of Open Discs. Figure 4 shows an annulus that is defined by two points on the outer circle and one on the inner circle. The blue arrow shows one Farthest Point Voronoi Edge and the green disc is one of the Open Discs.

Figure 4: An Annulus Defined By Two Points on the Outer Circle And One Point on the Inner Circle