The minimal enclosing circle problem (also known as the smallest enclosing circle or mininum spanning circle problem) is this: given a set of points on the plane, find the smallest circle which encloses all of them.
If your browser knows about Java and you have it enabled you should see an applet above. This applet allows you to experiment with minimal enclosing circle algorithm. Available commands are:
This applet implements the O(N log(N)) algorithm from Preparata and Shamos. The smallest enclosing circle of a set of points is defined by two or three points from the set. This algorithm proceeds in the following manner:
Both checking the set diameter and constructing the the farthest point Voronoi diagram take O(N log(N)) time, thus the entire algorithm only takes time O(N log(N)).
The algorithm used to calculate the convex hull is adapted from the LEDA C++ algorithm library. The LEDA implementation is based on a randomized incremental algorithm with running time O(N log(N)).
The set diameter calculation is performed using the rotating calliper algorithm from Preparata and Shamos. This performs a linear time search over the convex hull of the pointset.
As mentioned above, if the set diameter fails to enclose all the points then the minimal enclosing circle is defined by three of the points on the convex hull and the center is a vertex of the farthest point Voronoi diagram.
The farthes point Voronoi diagram is calculated using the method described by Skyum. This also takes O(N log(N)) time.The applet understands the following parameters:
|virtualwidth||integer||virtual canvas width||1000|
|virtualheight||integer||virtual canvas height||1000|
|backcolor||color name||background color||white|
|pointcolor||color name||point color||blue|
|hullcolor||color name||convex hull color||red|
|diametercolor||color name||set diameter and circle color||orange|
|meccolor||color name||minimal enclosing circle color||black|
|controls||boolean||user interface on or off||true|
|scrollbars||boolean||scrollbars on or off||true|
|hull||boolean||convex hull drawn||true|
|dcircle||boolean||diameter circle drawn||true|
|voronoi||boolean||farthest point voronoi diagram drawn||true|
|mec||boolean||minimal enclosing circle drawn||true|