329
edits
Changes
Jump to navigation
Jump to search
Parallel Enclosing Circle Algorithm (view source)
Revision as of 11:50, 6 October 2017
, 11:50, 6 October 2017no edit summary
Parallelization is implemented via Python2's [https://docs.python.org/2/library/subprocess.html#subprocess.Popen <code>subprocess.open()</code>] which is non-blocking and available in the standard library.
== The Problem ==
Rather, we seek to minimize the sum of enclosing circles containing at least <code>n</code> points.
Thus, multiple circles are allowed and inclusion in multiple circles is possible.
This algorithm has terrible time-performance characteristics, so we make the assumption that we can divide a large number of points with k-means and then solve those subproblems.
In other words, we make the simplifying assumption that the Enclosing Circle Algorithm has [https://en.wikipedia.org/wiki/Optimal_substructure Optimal Substructure].
== Parameters ==
This command will populate (and overwrite) any files in <code>data/</code>. The format of the filenames in this directory are <code>{city}{sep}{state}{sep}{year}{sep}{num}.tsv</code> where <code>num</code> is a 0-indexed integer of a split city/state/year <code>infile</code> that has greater than <code>SPLIT_THRESHOLD</code>
== Related Pages ==
