Parallel Enclosing Circle Algorithm

McNair Project

Parallel Enclosing Circle Algorithm
Project Information
Project Title	Parallel Enclosing Circle Algorithm
Owner	Oliver Chang
Start Date	July 31, 2017
Deadline	October 4, 2017
Primary Billing
Notes
Has project status	Complete
Is dependent on	Enclosing Circle Algorithm
Copyright © 2016 edegan.com. All Rights Reserved.

A thin-wrapper around the enclosing circle algorithm which allows for instance-level parallelization. This project consists of the python files in E:\McNair\Projects\OliverLovesCircles\src\python.

Parallelization is implemented via Python2's subprocess.open() which is non-blocking and available in the standard library.

The Problem

Note that this is not the classical enclosing circle algorithm. Rather, we seek to minimize the sum of enclosing circles containing at least n 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 Optimal Substructure.

Parameters

• in circles.py:
  • ITERATIONS: the number of iterations to attempt for each k to find minimum for that k
  • MIN_POINTS_PER_CIRCLE (AKA n): the minimum number of data points that must be included in a circle
• in vc_circles.py
  • NUMBER_INSTANCES: number of parallel instances to run; assume no data-races between instances
  • SWEEP_CYCLE_SECONDS: amount of time before removing completed jobs from the current job and adding new jobs if any files are left to process
  • TIMEOUT_MINUTES: maximum running time of a parallel instance of the algorithm
  • SPLIT_THRESHOLD: if a dataset has more than this threshold of data points, it will be split via k-means

Example Usage

$ python vc_circles.py --infile E:/McNair/Projects/OliverLovesCircles/CoLevelForCirclesNotRunGTE200.txt

where CoLevelForCirclesNotRunGTE200.txt is a tab-separated values file with the columns placestate, place, statecode, year, latitude, longitude, coname, datefirstinv, placens, geoid, city

This command will populate (and overwrite) any files in data/ and reports/. The format of the filenames in this directory are {city}{sep}{state}{sep}{year}{sep}{num}.tsv where num is a 0-indexed integer of a split city/state/year infile that has greater than SPLIT_THRESHOLD

Bugs/Issues

1. "St. Paul" and "St. Louis" have un-enclosed points--speculate because of weird file path issues
2. Some place/state/year combinations do not run to completion regardless of how tractable the number of points
3. How to merge small enclosing circles? This is a better measure of agglomeration regardless
4. How to separate outliers?

Plotting Circles

1. Connect to database with command psql -U postgres arc
2. password is tabspaceenter I think
3. \d lists tables
4. Now run SQL script LoadCircles.sql in OliverLovesCircles
5. Open ArcMap
6. Add data -> Top of file tree -> Database connection -> localhost for instance, database arc -> connect to localhost and table testcirclegeom
7. Add points from local files, make sure they are txt or tab files, not tsv

Related Pages

• Abhi's Rework (Summer 2017)
• Original Implementation (Spring 2017)

External Links

• Git Repository