[EM] A computationally feasible method (algorithmic redistricting)

[Kristofer Munsterhjelm]

Raph Frank wrote:
> On 9/2/08, Brian Olson <bql at bolson.org> wrote:
>>  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.
> 
> Your maps don't look like voronoi diagrams (edges aren't lines).
> 
> Do you assign based on
> 
> Assign voter to district with minimum
> 
>    distance to district centre - Cd
> 
> Where Cd is some coefficient for the district d. Cd is set so as to
> give equal populations.
> 
> If so, have you considered using squared distance instead of distance?
> 
> Assign voter to district with min
> 
>    (distance to centre)^2 - Cd
> 
> This gives straight district edges (I think).
> 
> You might need to change your rule to
> 
> The best district map is the one where people have the lowest average
> *squared* distance to the center of their district.

The reasonable thing to use would be Euclidean distance, since that 
makes sense, given the geometric nature of the districting problem. If 
you want to be even more accurate, you can use great circle distance 
instead to reflect that the districts are on the (near-)spherical Earth, 
but at the scales involved, the difference would be slight (and so it 
would be another "dotting the i-s" refinement :-)

Euclidean distance is simply, sqrt((x1-x2)^2 + (y1-y2)^2) for 2D. Since 
the Voronoi check would simply have to compare distances 
(nearest-neighbor), and the square root function is monotonic, one can 
cut it out to get (x1-x2)^2 + (y1-y2)^2.

The non-squared alternative is |x1-x2| + |y1-y2|, the Manhattan 
distance. It too would give straight lines (as opposed to curved ones), 
but more of them. I think Warren has an example of a Voronoi diagram for 
the Manhattan distance up on rangevoting somewhere (he used it to argue 
Range would produce better results than Condorcet in the case where 
voters have a preference distribution based on Manhattan distance). Some 
other Manhattan distance Voronoi diagrams can be seen here: 
http://www.nirarebakun.com/voro/eman.html

I may appear to be agreeing with you here, but the point of this 
explanation is to show that I don't think the artifacts you're seeing is 
  from him using Manhattan distance. In order to get curved results, you 
have to go to at least the L3 distance of (|x1-x2|^3 + |y1-y2|^3)^(1/3). 
That's a fairly strange metric, so I'm not sure why he gets curved 
district borders.

Also note that it's possible to find the borders of the Voronoi cells 
(for the Euclidean metric, at least) much quicker than doing a 
nearest-neighbor search on every single pixel. Quantization brought on 
by the varying sizes of census blocks may complicate matters, though.


Your reference to a Cd variable to get population proportionality is 
interesting. I think part of the problem that you're trying to fix here 
comes from that clustering (such as by Lloyd's algorithm) optimizes for 
energy instead of mass. Or in other words, it finds districts so that 
the average distance for each voter to the closest center is minimized 
(energy) rather than to find districts that have equal proportions of 
people within their borders (analogous to equal mass, if each voter is a 
point of unit mass).

Unless I'm mistaken, your generalization of Voronoi cells (with weights 
linked to the center nodes) is called power diagrams. Not long ago, I 
stumbled across a paper (draft?) about automatic redistricting involving 
power diagrams. It's here: 
http://www.stat.columbia.edu/%7Egelman/stuff_for_blog/fryer.pdf . The 
authors state that for a certain given compactness measure, the 
optimally compact district map will consist of power diagrams. They also 
give an algorithm for finding these optimal (or near-optimal, since the 
compactness measure is computationally intensive) power diagrams, but 
it's a bit too complex for my understanding.

>>  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.
> 
> Sounds reasonable.  However, people don't really like randomness.
> There is considerable resistance to using randomness in elections and
> people might consider a system where the solution isn't well defined
> as somewhat random.
> 
> "You mean that the best solution mightn't be picked because nobody
> could find it?"
> 
> Also, there could be issues if a better solution is found after the
> deadline, especially, if it favoured one party over another.
> 

Perhaps the randomness complaint could be diminished by having a default 
  map drawn according to some rules set in law. The redistricting law 
could refer to that rule, where the rule is very simple - perhaps 
splitline? Then a state commission or similar could draw the default map 
so that one is ensured that the results won't be too bad if the 
redistricting fails. As long as the rule is neutral, the state can't rig 
the default map, either.