Minimum Enclosing Circle using Simulated Annealing

The minimum enclosing circle is the smallest circle that contains all of a given set of points in the Euclidean plane. One solution to the problem of finding this circle is to use simulated annealing.

Simulated Annealing

Put simply, simulated annealing is an optimization technique. We start with an initial solution to the problem and look for a nearby solution. If this nearby solution is better than our initial solution, we update our solution. We repeat this until we can find a "good enough" solution.

The downfall of this method is that it is easy to fall into a local minimum trap, in which a seemingly optimal nearby solution is not actually globally optimal. However, we do not need to worry about ths in the minimum enclosing circle problem because distance functions are convex.

Sample Visualization

Number of points (10 ~ 300 inclusive):

Number of iterations (100 ~ 1000 inclusive):

How To Run

Above is a simple app using p5.js which simulates the simulated annealing solution. Here is how to use the app.

Input the number of points with your keyboard. This will set the number of points that will be generated randomly. This value must be an integer between 10 and 300 inclusive.
Input the number of iterations. This is the number of times the simulation will look for a nearby solution until it determines the solution to be "good enough". This value must be an integer between 100 and 1000 inclusive.
Click on the "Run!" button. The simulation will start running.

Once the visualization starts running, you will be shown:

The number of steps completed.
The radius of the current circle, 'r'.
The x coordinate of the center of the current circle, 'x'.
The y coordinate of the center of the current circle, 'y'.
The circle of the current step as a red circle (turns green upon completion).

The radius of the current circle, 'r'.
To change some parameters and re-run the visulation, change the values in the appropriate fields then simply click the button again. In fact, it may be interesting to see how the accuracy of the process changes or how drastic the updates get based on the parameter values.