Modern Solutions

This page is a little more technical than the remainder of this site, so if you get confused, or find the concepts unfamiliar, proceed ahead to the applet or other sections of this site. This section is for those interested in the nittygritty details of the problem. 
It remains to prove that the algorithm will converge towards an answer, rather than looping forever. The proof follows from the fact that, at each iteration of the algorithm, we are reducing the radius of the circle being considered, while ensuring that all the points of the set are still within that circle. Thus the circle will converge towards the MEC.
Why did we not use the linear time algorithm? Look at it, it is
detailed below. This algorithm requires the implementation of linear
time median finding algorithms, and is generally far more complicated
than the approach we took. In our approach, we greatly reduce the data
we work on by first finding the convex hull, and then use a polynomial
time solution on the reduced data set. For the specific
implementation in an applet, we did not expect our data volume to
be large enough to warrant the overhead involved in the linear time
approach. When all is said and done n^{3} for 10 points or so is
going to be faster than 50n for 100 points.
Furthermore, what we are more interested in is the performance of the
algorithm in terms of incremental changes to the data. We would like a
fast way to add one point to the data, and patch up the MEC without
having to recompute everything. To do this, we run the main loop of
the algorithm with S initialized to be the last side considered when the
MEC was last computed. For the addition of a single point, we expect
this to have a significantly better expected running time than starting
with an arbitrary side.
Finally, and to everyone's surprise, Nimrod Megiddo showed in 1983 that his ingenious pruneandsearch techniques for linear programming could be adapted to find the minimal enclosing circle in O(n) time. Furthermore, the linear algorithm requires no more than high school mathematics to be understood and proved correct, and (as refined by Dyer in 1984) makes no generalposition assumptions about the input data. This landmark result is among the most beautiful in the field of computational geometry.
For example, suppose 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. So 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) medianfinding algorithms. However, he was the first to apply it to a number of fundamental problems in computational geometry.
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, >)
MECcenter(S, L)
median()
predates Megiddo's work, whereas
the algorithm described here as MECcenter()
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 pruneandsearch to run in linear time.
The algorithm used by MECcenter()
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 yvalue.
Call this yvalue y_{mid}.
MECcenter()
to find which side of the line
y=y_{mid} the MECcenter C lies on. (Without loss of generality,
suppose it lies above.)
MECcenter()
on L. Without loss of generality, suppose
C lies on L's right.
MECcenter()
, we have found that the MECcenter 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 which 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, colinear points, etc), but it turns out that we get the same performance guarantees for such cases  in fact, for degenerate input the algorithm is able to discard more than n/16 points. In short, no matter what the input, we are guaranteed to prune at least n/16 points at each iteration. So, by the fundamental argument from the geometric series, Megiddo's algorithm computes the minimal enclosing circle in linear time.