# [EM] More on Gerrymander prevention

Forest Simmons fsimmons at pcc.edu
Thu Mar 28 16:11:09 PST 2002

```On Mon, 25 Mar 2002, Adam Tarr wrote:

> Josh wrote:
>
> >
> >Dense networks of roads should not be separated into separate districts.
> >An urban area on two sides of a bridge could easily be divided.
>
> Very slick idea Josh.  The question becomes, how do you come up with a
> measure of road connectivity?  I would propose basing it on the same
> principles as electrical resistance.  The "resistance" of a road connecting
> two points is proportional to its length, and inversely proportional to the
> number of lanes.  Find the "resistance" of every road connecting two
> adjacent census blocks, and add them in parallel (1/total = 1/first +
> 1/second + ...).  Invert this total resistance to get the "conductance" or
>
> Build a graph (computer science-type graph, with nodes and edges) out of
> the census blocks, with each edge (border) weighted by the connectivity
> between those two nodes (census blocks)  Now, we just tell the algorithm to
> build equal-population districts that maximize total connectivity.  It's a
> well-defined graph theory problem.

There's probably an effective algorithm for optimization, too.  If not,
choosing among proposed solutions would be effectively computable.

I was thinking along similar lines, except I was thinking of defining a
metric in terms of the expected time to make the round trip from point A
to point B and back under average traffic conditions (while respecting the
speed limit).

Note that the three basic metric conditions are satisfied:

Symmetry condition:  d(A,B)=d(B,A)  [That's why I said "round trip."]

Triangle inequality:  d(A,C)+d(C,B) >= d(A,B)
[Optimal round trip is not made longer by removing a constraint.]

Separation condition:  d(A,B)=0 if and only if A=B.
[Unless you believe in time travel.]

Those rental cars that come equipped with GPS systems already have
the problem essentially solved, at least for cities with airports.

I was thinking in terms of Dirichlet regions for this metric, but I like
Adam's idea of working in terms of the connectivity of a graph whose nodes
are the census blocks much better.

Forest

```