Project Nayuki

Smallest enclosing circle


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

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(n4) algorithm. Thus it can handle thousands of points with ease.

Source code





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