[EM] A computationally feasible method (algorithmic redistricting)

[Brian Olson]

On Sep 1, 2008, at 7:28 AM, Kristofer Munsterhjelm wrote:

> A simpler algorithm, though one that doesn't give any worst-case  
> bounds, is Lloyd's algorithm. Start with random center points, then  
> calculate the centroids for the current Voronoi cells. Move the  
> center points towards the centroid (shifting the Voronoi cell  
> somewhat) and repeat. Do so until they settle. This can get stuck in  
> a local optimum.

I have implemented essentially that, and it pretty quickly gets pretty  
good results as measured by the "distance per person to land-area- 
center" test. I added one thing to deal with variations in population  
density. Each district center also has an associated weight. Each  
'voronoi cell'/district contains the people with a weighted distance  
closest to that district center. So, a district center in a high  
population density area doesn't have to reach very far to gather its  
allotment of people.

There are some states where this doesn't work very well (CA, TX, NV,  
and a couple others) and a more exhaustive solving method is needed. I  
think one of the weaknesses of the voronoi method is that population  
is not continuous, but in discrete census blocks of dozens to  
thousands of people. The voronoi method can't necessarily tweak to  
swap a block here and a block there to get within a reasonable margin  
of equal-population.

I think it's worth repeating that I'd prefer to write the law with a  
way of measuring what a good district mapping is, rather than writing  
the law with a specific procedure for creating the district mapping.  
Specific procedures get really complex, and I don't think in this case  
that a fair procedure ensures a fair outcome. I used the voronoi  
technique as just one possible way of writing a solver to get the  
desired result. It could even wind up that the best way to solve for  
the desired goals is to have a computer do 99% of the work and have a  
human come back and clean up the edges. Since it's subject to the same  
scoring in the end, the human couldn't deviate too far from the ideal  
mapping.


Brian Olson
http://bolson.org/