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:

**Mouse button 1**- Create or move a point
**Mouse button 3 (or Meta-Mouse)**- Delete a point
**Scrollbars**- Move around the virtual canvas
**"Convex hull"**- Toggles the drawing of the convex hull
**"Set diameter"**- Toggles the drawing of the set diameter
**"Set diameter circle"**- Toggles the drawing of the set diameter circle
**"Voronoi diagram"**- Toggles the drawing of the farthest point Voronoi diagram
**"MEC circle"**- Toggles the drawing of the minimal enclosing circle
**"Clear"**- Erases all points

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:

- Calculate the set diameter
- Check if the set diameter encloses all of the points. If so, quit.
- Calculate the farthest point Voronoi diagram and find the minumum
circumradius associated with each of the
*N*vertices. This Voronoi vertex with the mininal circumradius is the center of the minimal enclosing circle.

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.

Name | Data type | Description | Default |
---|---|---|---|

virtualwidth | integer | virtual canvas width | 1000 |

virtualheight | integer | virtual canvas height | 1000 |

pointsize | integer | point size | 10 |

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 |

pointXXX | integer,integer | point position | |

hull | boolean | convex hull drawn | true |

diameter | boolean | diameter drawn | true |

dcircle | boolean | diameter circle drawn | true |

voronoi | boolean | farthest point voronoi diagram drawn | true |

mec | boolean | minimal enclosing circle drawn | true |