What is the best way to search for an annular object? Such problems arise in situations as diverse as meteorite craters and the spread of infections. Previous methods of spatial searching have normally looked for rectangles or ellipses and do not find objects with holes. The sequence of algorithms needed for finding rings, as presented in this paper, are:

(1) How to efficiently locate both the center and radii of the desired circles when the information is presented on a rectangular grid;

(2) How to use different search pruning methods for the search for the center of a ring and the search for the edges of that ring; and

(3) How to verify that a proposed ring has a desired level of statistical significance, by comparing with Monte Carlo random data.

The paper concentrates on efficiency as well as accuracy, by using pruning methods to find answers quickly and adapting search precision to avoid either missing rings or using too much computation. Their acronym DGPLMR includes the concept of dual grid (for center and radii), pruning (in the search), local maxima elimination (find the best ring in each area), multi cell size for searching the ring width, and refine (a final process to choose the ring coordinates accurately).

The method was evaluated on both randomly generated sample data and on a real set of data from an outbreak of Legionnaires’ disease in New York City. They compared it with previous algorithms such as SaTScan (in wide use but not tailored to rings) and also with simpler versions of their approach. Their final algorithm both finds more target rings and runs faster. The paper is mathematical though quite clear, and contains useful code sections as well as theoretical complexity bounds. It is recommended to experts in searching for shapes in image data.