What is the Problem?
|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.|
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.)
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(n2).