7,612
edits
Changes
Jump to navigation
Jump to search
|Is billed to=|Has notes=|Has project status=ActiveSubsume|Is dependent on=|Depends upon itHas Image=Red-circle.jpg
Enclosing Circle Algorithm (view source)
Revision as of 13:47, 21 September 2020
, 13:47, 21 September 2020no edit summary
{{McNair ProjectsProject|Has project output=Tool|Has Imagesponsor=Red-circle.jpgMcNair Center
|Has title=Enclosing Circle Algorithm
|Has owner=Christy Warden, Peter Jalbert,|Has start date=201701January 2017|Has deadline=201704April 2017
|Has keywords=Tool
}}
The objective of this project is come up with a fast, reliable algorithm that finds the smallest circle area that can drawn around N Cartesian points such that each circle contains at least M<N points. This algorithm will be used in an academic paper on [[Urban Start-up Agglomeration]], where the points will represent venture capital backed firms within cities.
8) Choose the scheme that resulted in the smallest total area.
=Alternative K-Means Based Algorithm=
==Location==
The script is located in:
6. for node in valid_nodes, add node to explored_nodes, change cur_node to node, and update respective areas, parents, children, circle, points
7. run this algorithm again, change k = 2
8. if the cur_node cannot be split into 2, or the cur_node cannot be split into 2 circles with smaller areas than its parent, add cur_node to end_nodesand resume algorithm with next valid_node not in explored_node as the cur_node
9. if all the valid_nodes are in explored_nodes, return end_nodes
10. repeat the above algorithm for all k from 2 to int(#number of total points/n) and take the end_nodes with the lowest total area
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. <br>
Further improvements could implement an early-stopping method to converge to a local optima. <br> ==Comparison to Other Algorithm ==The K-Means based algorithm returns the optimal solution, albeit slower ( 12 seconds vs. .07 seconds) <br>
==Visualization ==
The K-Means based algorithm returns the optimal solution, albeit slower <br>
[[File:kmeans comparison.png]] [[File:kmeans random.png]] [[File:houston.png]]
=Brute Force=
