Minimum enclosing ball

Computational geometry is full of algorithms that demonstrate how randomization very often leads to simplification. One example is the famous randomized incremental algorithm for finding the minimum enclosing ball of a set of points in d-dimensions. The idea of the algorithm is very simple. All you need to do is to look at the points in a random order and maintain the minimum enclosing ball (MEB) of the points seen till now. When a new point is considered, if it already lies inside the current MEB, then there is no need to do anything, but if it lies outside, then update. With some math it can be shown that the expected amount of time this algorithm will take is linear. This is at par with the best known deterministic algorithm known at the time of discovery of this algorithm. However, the deterministic algorithm was quite complex and not easily implementable.

Here’s a very nicely written paper that describes the algorithm – http://www.springerlink.com/content/ph273841264x5163/

Advertisements