Minimal Enclosing Circle

Introduction

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.

Demonstration

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

Algorithm

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:

  1. Calculate the set diameter
  2. Check if the set diameter encloses all of the points. If so, quit.
  3. 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)).

Implementation

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:
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