The minimal enclosing circle is used in planning the location of a shared facility. For example, a shared facility is a hospital servicing a community. Note that traditionally people consider post office as an example hence post office problem (see Voronoi diagram). If we consider each home in a community as points in the plane, finding minimal enclosing circle gives a good place to put the hospital i.e., the center of the minimal circle. Placing the hospital at the center of minimal circle minimizes the distance between the hospital and the farthest home (point) in the community.
In the military, this problem is known as the “Bomb Problem”. If we suppose each target on a map as a planar point, the center of the minimal circle of a map i.e., set, is a good place to drop a bomb for maximum destruction. Furthermore, the radius of the minimal circle can be used to calculate how much explosive is required.
This problem is also useful to examine the point that lie on the boundary of the minimal enclosing circle. These points are in a sense the outliers of the set, and in statistics, are sometimes discarded to get a more robust estimate.
The simplest algorithm considers every circle defined by two or three of the n points, and finds the smallest of “these” circles that contains every point. There exits O(n^{3}) such circles, and each takes O(n) time to check, for a total running time of O(n^{4}). Elzinga and Hearn gave an O(n^{2}) algorithm in 1972, and Shamos and Hoey (1975), Preparata (1977), and Shamos (1978) discovered the first O (n logn) algorithms.
Finally, and to everyone's surprise, in 1983 Nimrod Megiddo showed that the minimal enclosing circle problem can be solve in O(n) time using the prune-and-search techniques for linear programming. This landmark result is one of the most beautiful in the field of computational geometry.
The Minimal Enclosing Circle Problem is, simply stated, the problem of finding the smallest circle that completely contains a set of points. Formally, given a set S of n planar points, find the circle C of smallest radius such that all points in S are contained in either C or its boundary.
This algorithm is straight forward, but expensive to implement. Step 1, 2 and 3 require linear time in the number of points in the given set. 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^{2}).
The remaining section is divided into two parts. First part describes the algorithm used in implementation and the second part presents the best-known algorithm for finding minimal enclosing circle, MEC.
This algorithm is due to Pr. Chrystal (1885).
Foremost, observe that the minimal enclosing circle, MEC, is entirely determined by the Convex Hull of a given set of point. The reason is the points of the set touched by the minimal enclosing circle are always on the convex hull of the set.
First step of the algorithm is to compute the convex hull, H, of the points in linear time. Clearly, we can do this since points are kept ordered by x-coordinate. Call the convex hull H and the number of convex hull vertices h. Next step is to pick any side, say S, of the convex hull. The main loop of the algorithm is as follows:
Assuming the points are given in sorted order, the
algorithm initializes in the time that is linear in the number of points in the
set. The main loop of the algorithm requires linear time with respect to the
number of convex hull points, and main loop could be repeated once for each
diagonal of the convex hull. The number of diagonals is proportional to the
square of the number of convex hull points.
For that reason in the worst case, the total time of the algorithm is
proportional to the number of points in the set, plus the cube of the
number of convex hull points.
However, in implementation, the running time depends on the side initially
chosen to start the algorithm, and the algorithm expected to perform quite well
in practice.
It remains to prove that the algorithm will defines the minimal enclosing circle of the given set of points, rather than looping forever. The proof follows from the fact that during each iteration, algorithm is reducing the radius of the circle being considered and ensuring that all the points of the set are still within the circle. Therefore, the circle will eventually become the minimal enclosing circle.
Nimrod Megiddo proposes the algorithm and it uses the prune-and-search techniques for linear programming to find the minimal enclosing circle in O(n) time.
The essence of Megiddo's algorithm is prune-and-search. In a prune-and-search algorithm, a linear amount of work is done at each step to reduce the input size by a constant fraction f. If this can be achieved, then the total amount of work done will reduce to O(n)*(1 + (1-f) + (1-f)^{2} + ...). In this formula, the infinite series is geometric and sums to a constant value, and so the total running time is O(n). For example, suppose that by inspecting our set of n input elements we can discard 1/4 of them as irrelevant to the solution. By repeatedly applying this inspection to the remaining elements, we can reduce the input to a size which is trivial to solve, say n≤3. The total time taken to achieve this reduction will be proportional to (n + 3n/4 + 9n/16 + ...). It is easy to show that this series approaches, and never exceeds, a limit of 4n. Therefore, the total running time is proportional to n, as required.
The idea of using the geometric series to reduce an algorithm to linear time predates Megiddo's work; in particular, it had previously been used to develop O(n) median-finding algorithms. However, he was the first to apply it to a number of fundamental problems in computational geometry.
To find the minimal enclosing circle (MEC) of a set of points, Megiddo's algorithm discards at least n/16 points at each (linear-time) iteration. That is, given a set S of n points, the algorithm identifies n/16 points that can be removed from S without affecting the MEC of S. This procedure can be repeatedly applied until some trivial base case is reached (such as n=3), with the total running time proportional to (n + 15n/16 + 225n/256 + ...) = 16n.
In order to find n/16 points to discard, a great deal of cleverness is required. The algorithm makes heavy use of two subroutines:
median(S, >)
MEC-center(S, L)
As mentioned above,
median()
predates Megiddo's work,
whereas the algorithm described here as
MEC-center()
was presented as part
of his 1983 paper. To explore these procedures in detail would go beyond the
scope of this outline, but each uses prune-and-search to run in linear time. The
algorithm used by
MEC-center()
amounts to a
simplified version of the algorithm as a whole.
Given these primitives, the algorithm for discarding n/16 input points runs as follows:
median()
to find the bisector
with median slope. Call this slope m_{mid}.
median()
to find the point in I
with median y-value. Call this y-value y_{mid}.
MEC-center()
to find which side
of the line y=y_{mid} the MEC-center C lies on. (Without loss of
generality, suppose it lies above.)
MEC-center()
on L. Without loss
of generality, suppose C lies on L's right. We can now discard one point in S for each of the n/16
intersection points in I''. The reasoning runs as follows. After two calls to
MEC-center()
, we have found that the MEC-center C must lie
above y_{mid} and to the right of L, whereas any point in I'' is below y_{mid}
and to the left of L.
Each point in I'' is at the meeting point of two bisector lines. One of these bisectors must have slope ≥ m_{mid}, and therefore must never pass through the quadrant where we know C to lie. Call this bisector B. Now, we know which side of B C lies on, so of the two points whose bisector is B, let P_{C} be the one that lies on the same side as C, and let the other be P_{X}.
It is easy to show that P_{C} must be nearer to C than P_{X}. It follows that P_{C} cannot lie on the minimal enclosing circle, and thus we can safely discard a point P_{C} for each of the n/16 intersection points in I''.
We have not discussed here how this algorithm can be made to deal with degenerate input (parallel bisectors, collinear points, etc), but it turns out that we get the same performance guarantees for such cases. The fact of the matter is for degenerate input the algorithm is able to discard more than n/16 points. In short, Megiddo's algorithm guarantees to prune at least n/16 points in each iteration independent to input.
Therefore, by the argument based on the geometric series, Megiddo's algorithm computes the minimal enclosing circle in linear time.