[EM] Advantages of Dirichlet Region Districts

[Forest Simmons]

On Thu, 15 Jan 2004, Alex Small wrote:

> Forest suggested that election districts should be drawn by defining a
> center for each district, and specifying that district i will be the set
> of all points which are closer to center i than any other center.  He
> suggested that "closer" be measured by (literally) taxicab geometry.
>
> I like this notion of taxicab geometry relying on roads, but I think one
> should also specify a limit to resolution.  I wouldn't want to
> artificially divide neighborhoods, so I might specify that the only roads
> considered for these purposes are those with speed limits of 35 mph or
> greater.

Suppose that your house is on a street with speed limit 20 mph. Then the
shortest route from your house to a major road should also be included in
the network.  I think this is what MapQuest does when it suggests the best
route from point A to B (rather than taking you through back alleys, etc.)

>
> Also, a question for Forest and others:  Perhaps this was already
> addressed and I just missed it, but does the Dirichlet method minimize any
> criterion such as total perimeter, or satisfy some criterion regarding
> convexity of districts or whatever?
>

If the Euclidean metric were used, it would give convex districts.

Imagine what would happen if you decided to put all of the centers at
different distances from each other on the same line of longitude.  Each
region would be long and narrow, but convex.

That's why I suggested using a measure of over-all compactness
(specifically the within district average distance between voters) to
choose among the various Dirichlet proposals (indeed, to choose among all
of the proposals, Dirichlet or not).


> Finally, I do have one reservation about the Dirichlet method:  In order
> to achieve (roughly) equal population, one must do a considerable amount
> of trial and error, adjusting district centers until the population
> variance is below some pre-determined criterion.  Does anybody have
> thoughts about how to handle this problem tractably?
>

One of the reasons I withdrew the Dirichlet requirement is that I found an
example that shows it isn't always possible to satisfy the equal
population requirement with Dirichlet regions.

Imagine an island in which all of the houses are located along a 120 km
stretch of straight road, which runs the entire length of the island.
Suppose there are 100 voters evenly distributed along the first ten km and
the same along the last ten km and the same evely distributed along the
middle 100 km.  Suppose that there are to be three districts with 100
voters each.

Then the boundaries have to be at the ten km and 110 km markers.

This cannot be done with Dirichlet regions (unless the two extreme
district "centers" are several km out to sea).

Building on this example, you can see that it is completely impossible to
find (five) Dirichlet regions (intervals) on a straight line whose
boundaries are at 0, 10, 110, and 120.

If it cannot be done at all, then it cannot be done tractably:-)

One can rescue the situation by allowing two adjacent regions to coalesce
(i.e. by having two centers for the big center region in our example) or
by having different speed limits in different regions, and using min
travel time as the metric (i.e., make the speed limit ten times as fast in
the center region in our example).

But since we abandoned the Dirichlet requirement, these are merely
suggestions for the partition designer ... grist for the DNA computer
searching for a competitive proposal.

Forest