The O(n log n) Algorithm

The algorithm to produce a minimal width annulus to cover a point set of n points (given a constraint of a fixed inner circle radius) is not complex. It accomplishes its task in a worst case time of O(n log n). It consists of two steps:

1. Generating an O(n) list of candidate centers. This step may take (in the worst case) O(n log n) time.
2. Finding the center that produces the minimal width annulus. This step may also take (in the worst case) O(n log n) time.

Since the Center Lemma lists four types of locations where the center of a minimal width annulus (with fixed inner circle radius) can be located, this step can be accomplished by computing and enumerating the candidates for each type of location. The types of locations are:

• the centers of diametral pairs;
• the Farthest Point Voronoi Vertices;
• the intersection point of a Farthest Point Voronoi Edge and the Boundary of the Union of Open Discs; or
• a vertex of the Union of Open Discs.

A diametral pair is a set of two points such that distance between the two points is greater than or equal to the distance between any other pair of points. An obvious O(n²) method to compute the centers of all diametral pairs is to compute the centers of all pairs. Preparata and Shamos discusses how this can be computed in O(n log n) time.

An obvious brute force method to compute all of the Farthest Point Voronoi Vertices is to compute the intersections of the bisectors of all pairs of points. Berg et al discusses how this can be done in O(n log n) time.

An obvious brute force method to compute all the intersections is to compute the intersection of the bisectors of all pairs of points with every open disc. Berg et al discusses how this can be done in O(n log n) time.

An obvious brute force method to compute all vertices of the Boundary of the Union of Open Discs is to simply compute all intersections of open discs. Aurenhammer discusses how this can be done in O(n log n) time.

After we have identified the O(n) candidate centers we will spend at most log n time evaluating each candidate. Thus this step will take at most O(n log n).

Kirkpatrick discusses how to determine in which cell of the Farthest Point Voronoi Diagram a candidate point lies in O(log n) time (after an O(n) preprocessing step). Using a similar technique it is possible to determine whether the annulus is feasible (does the inner circle contain points). The distance between the candidate and the generator of the cell containing the candidate is the minimum possible length of the outer circle radius. Since the inner circle radius is fixed, the best candidate is the one corresponding to the smallest outer circle radius.