[EM] Re: Automated districting

[Adam Tarr]

We talked about districting here in the spring of 2002, and came to what 
seemed to be a satisfying conclusion to me:

http://groups.yahoo.com/group/election-methods-list/message/9223

Thumbnail sketch of the proposed idea:

1)  Treat the census blocks as "atoms" of the eventual districts, i.e. they 
cannot be split up into two districts.

2)  Form a graph of the states where the nodes are census blocks, and the 
edges represent physically adjacent census blocks.

3)  Weight each edge by the amount of road connectivity between the 
adjacent bolocks.  The simplest metric would be number of lanes of traffic 
that fall on the dividing line.  Basically, you want the edge weight to 
represent how connected those two census blocks are in reality.  Ideally, 
what you'd want is a count of how many people cross the border per year, 
but that's obviously unrealistic, so the road bandwidth is a good 
approximation.

4)  When you set up districts, you are essentially taking the large graph 
of the entire state and dividing it into several small sub-graphs which 
each represent a district.  To do so, you cut every census block-to-census 
block edge along the district boundary.

5)  THE AUTOMATED ALGORITHM would take the weighted graph that represents 
the entire state, and divide it up into the equal population solution THAT 
MINIMIZES the total weight of the severed edges.

Such an algorithm may be difficult to write, but writing a program that 
could iterate on an approximate solution could be pretty easily.

-Adam