What is the Problem?

Problem Statement

More formally:

Given a set S of n points in the plane, find the circle C of smallest radius with the property that all points in S are contained in C or its boundary.

Applications

In the military, the minimal enclosing circle is known as the Bomb Problem. If the points in the set are viewed as targets on a map, the center of the minimal circle surrounding them is a good place to drop a bomb to destroy the targets, and the circle's radius can be used to calculate how much explosive is required.

If we want to rotate a set of points into any arbitrary alignment, e.g. rotate the shape to make the line connecting some two chosen points vertical, then the minimal enclosing circle of the points is the amount of space in the plane that must be empty to permit this rotation.

The minimal enclosing circle provides a rough approximation to its points. In other words, any application involving a test of proximity between sets of points and a new point could benefit from having computed the minimal enclosing circles of the point sets to quickly determine whether the new point is close to a given set.

It can also be useful to examine the points which lie on the boundary of the minimal enclosing circle. These points are in a sense the outliers of the set, and in statistics they are sometimes discarded so that estimates are more robust. This discarding process can be repeated to make the data set more concentrated.

The points which lie on the boundary of the minimal enclosing circle are The diameter of the minimal enclosing circle provides an approximation to the span of the point set. It can be shown that it is no more than a factor of sqrt(3) larger than the span.
(NB: The span of a point set is the maximum distance between two points in the set.)

An Intuitive Solution

1. Draw any circle around all the points. This circle can clearly be made smaller.
2. Make your circle smaller by finding the point A farthest from your circle's center, and drawing a new circle with the same center and passing through the point A. This produces a smaller enclosing circle, since it still contains all the points, but now passes through A rather than enclosing it.
3. If the circle passes through 2 or more points, proceed to step 4. Otherwise, make the circle smaller by moving its center towards point A, until the circle makes contact with another point B from the set.
4. At this stage, you will have a circle, C, passing through two or more points from the set. If the circle contains an interval of arc greater than half the circle's circumference on which no points lie, the circle can be made smaller. We will call such an interval a point-free interval. Let D and E be the points on the ends of this point-free interval. While keeping D and E on the circle's boundary, reduce the diameter of the circle until
   1. the diameter is the distance DE, or
   2. the circle C touches another point from the set, F.
   In case a), we are finished. In case b), we must check whether there are now no point-free arc intervals of length more than half the circumference of C. If there are none, we are done. If there does exist such a point-free interval, we need to repeat step 4. In this case, three points must lie on an arc less than half the circumference in length. We repeat step 4 on the outer two of the three points on the arc.

Step 1 requires linear time in the number of points in our set, as does step 2. Step 3 is also linear in the number of points. In step 4 above, it takes linear time to find each new point F.
However, finding the point F does not guarantee the termination of the algorithm. Step 4 must be repeated until the circle contains no point-free interval longer than half its circumference.
In the worst case, this requires n-2 iterations of step 4, implying that the total time spent in step 4 could be on the order of the square of the size of the point set.

Hence this algorithm is O(n²).

Home  Next