Smallest Enclosing Circle

Problem Statement

The Smallest Enclosing Circle problem (also known as Minimal Enclosing Circle problem in the literature) is the problem of finding the smallest circle that completely contains a given set of planar points. Formally, given a set of S of 2D points, find the circle C with the smallest radius such that all the points in S are contained in either C or its boundary.

Demonstration

The following applet Computes the Smallest Enclosing Circle of a set of 2D points. The algorithm used in the applet was developed by Welzl [1]. The usage of the applet is as follows:
  • Click the left mouse button to add a point.
  • The Smallest Enclosing Circle is draw in yellow.
  • Drag any point to see how the solution changes.
  • Click the button "Reload" to restart the applet.

Source files

Here are the Java source files of the above applet.
Point.java
Circle.java
SEC.java

References

[1] E. Welzl, "Smallest enclosing disks (balls and ellipsoids)",Lecture Notes in Computer Science, Vol. 555, 1991, pp. 359-370.