# The constrained minimum-width annulus of a set of points

by Emory Merryman

# Introduction

### Annuli Are Doughnuts! (sort of)

Formally, an annulus is the area bounded by and contained within two concentric circles. This geometric construction is also known as a "doughnut." (However as Figure 1 shows, not all doughnuts are annuli.)

### What is a Minimum-Width Annulus?

The width of an annulus is the difference between the radii of its two defining circles. Usually an annulus is covering a set of points. If the annulus is minimum width then

• if we increased the inner radius (reducing the width) then some points would no longer be covered; and
• we decreased the outer radius (also decreasing the width) then again some points would no longer be covered.

Figure 2 shows an annulus that covers several points. The annulus itself is light blue. As you can see it is defined by two concentric circles - the inner circle and the outer circle. Both the inner and outer circle are shown in dark blue. The points are depicted as red dots. You can think of this annulus as a blueberry doughnut with red sprinkles if you like. This is how this project graphically depicts annuli.

I will not try to formally argue that Figure 2 is a minimum width annulus. In this case, it should be obvious from visual inspection. But informally, it should be clear that you can not make the inner circle any bigger nor the outer circle any smaller and still cover the point set. Thus the width of the annulus can not be made smaller.

#### Variation of the Problem

There are several interesting variations on the minimum-width annulus problem. I will briefly introduce three: the fixed outer radius, the fixed inner radius, and the fixed median radius. However for simplicity throughout the rest of this web tutorial, I will only discuss the fixed inner radius variation. If you are interested in the other variations, then I invite you to read a more advanced reference

In the fixed outer radius variation, the radius of the outer circle is fixed at a specified value. The radius of the inner circle can be as small as a point (for the fattest possible annulus) or as large as the outer circle (for the thinnest possible annulus).

It should be trivial to see that it is sometimes impossible to produce a single annulus that covers a given point set with this restriction. Figure 3 illustrates a point set where it is impossible to produce a single covering annulus (with the specified outer circle radius). As you can see, it does not matter what size the inner circle is. The outer circle simply can not cover all the points.