|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 nitty-gritty 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 n3 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 prune-and-search 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 general-position 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) median-finding 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()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 mmid.
median()to find the point in I with median y-value. Call this y-value ymid.
MEC-center()to find which side of the line y=ymid 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.
MEC-center(), we have found that the MEC-center C must lie above ymid and to the right of L, whereas any point in I'' is below ymid 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 >= mmid, 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 PC be the one which lies on the same side as C, and let the other be PX.
It is easy to show that PC must be nearer to C than PX. It follows that PC cannot lie on the minimal enclosing circle, and thus we can safely discard a point PC 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.
Prev Home Next