|Does subsume=Enclosing Circle Algorithm, Enclosing Circle Algorithm (Plotting),
}}
=K-Means Based Algorithm=
==Location==
The script is and associated modules are located in: E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)\enclosing_circle_new_implement.py
==Explanation==
The algorithm relies on an object -oriented implementation of a "cluster". <br>
Each "cluster" has the following associated with it: <br>
1. area of minimum circle enclosing points in the cluster
'''Runtime:'''
The runtime of the minimum enclosing circle is O(n), and the runtime of constrained k-means depends on k itself. Here, the value of k is proportional to the total number of points. <br>
We would expect the algorithm to slow as the number of points increase. For reference, a set of 80 points with n =3, took about 30 minutes, with the number of iterations at 100. <br>Further improvements could implement an early-stopping method to converge to a local optimaoptimum. <br> [[File:runtime.png]]
==Visualization ==
The K-Means based algorithm returns the optimal solution(left), albeit slower and faster. <br>[[File:houstonk.jpgpng]] [[File:houstonp.jpgpng]] == Benefits ==Is faster than both Brute Force and Logical Enclosing Circle. <br>Is more accurate than Logical Enclosing Circle. <br>Can plot to google maps. <br>Will return a tab delim text file of the following fields: city, year, total area <br>Good for a large number of points <br> ==Drawbacks==Is not the optimal solution as number of points increases, but an approximation =Logical Enclosing Circle===Location==The python script is located in : E:\McNair\Projects\Accelerators\Enclosing_Circle\Enclosing_Circle\EnclosingCircleRemake2.py==Explanation==The rationale is to take the furthest point, draw a circle with its nearest n-1 points. <br>Take the furthest point from the initial point, draw a circle with its nearest n-1 points. <br>Repeat until all points are enclosed. <br>==Benefits==Can plot to google maps <br>Is faster than brute force <br>Returns city, circles, year to a tab delimited text file <br> ==Drawbacks==Really slow for large number of points <br>Offers an approximate solution that is worse than the Clustering based version <br>
=Brute Force=
The Julia Script is located in:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle