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/ ---- Election-Methods mailing list - see http://electorama.com/em for list info
