# Smallest enclosing circle

## Description

This JavaScript program computes the smallest circle that encloses a given set of points in the plane. Instructions:

- Left click: Add point or move existing point. Drag to move the point.
- Right click: Delete point.

Although the problem looks easy to solve visually, the algorithm is in fact moderately long and quite tricky. (This deceptive difficulty is a common theme in computational geometry.) I don’t fully understand how to solve this problem from scratch, and my program’s implementation relies heavily on the mathematics and reasoning covered in the PDF below. This randomized algorithm runs in expected linear time, unlike the naive `O`(`n`^{4}) algorithm. Thus it can handle thousands of points with ease.

## Source code

Java:

- smallestenclosingcircle.java (computation functions)
- smallestenclosingcircletest.java (JUnit test suite)

JavaScript:

- smallestenclosingcircle.js (computation functions)
- smallest-enclosing-circle-demo.js (the demo on this page)

Python:

- smallestenclosingcircle.py (computation functions, compatible with Python 2 and 3)

C#:

- smallestenclosingcircle.cs (computation functions)

The Java version is considered the reference version because it has object types and the code is structured more clearly. License: GNU Public License v3.0+

## More info

- Wikipedia: Smallest-circle problem
- Geometric Algorithms: Smallest enclosing circles and more (Utrecht University) (PDF)