[EM] Re: Compactness

[Forest Simmons]

Another intrinsic approach:

Suppose that the census bureau published a data base representing a
network whose nodes were the voter residences and whose edges were the
streets and roads.  Weights on the nodes would give numbers of voters,
weights on the edges would be either numbers of meters or standard travel
times in seconds between centers of residences represented by the incident
nodes.

A districting proposal would be a partition of the given nodes. Each class
of nodes within a proposal would be required to represent the correct
number of voters within specified tolerances.

For each district the weight of a minimum weight spanning tree would be
calculated (by Kruskal's algorithm, say).  The sprawl of a districting
proposal would be measured by the sum of its district weights.

The least sprawl proposal would be adopted.


Now, one more example of why I would use "real taxi fare" distance over
Euclidean distance, even though that would preclude the use of the
parallel axis theorem, etc.


Imagine a rectangle (representing a municipality) centered on the origin
of a Cartesian coordinate system ... sides parallel to the axes, and the
upper right corner located at (11, 50), and the curve given by the
equation y = (x^3 - 75*x)/10 representing a river cutting the rectangle
into two equal area pieces.

A bridge centered at the origin (0,0) connects the two congruent pieces.
This bridge is the only river crossing.


Suppose that the municipality has population distributed with central
symmetry, i.e. if there is a voter at position (x,y), then there is one at
(-x,-y).

Suppose further that the population is spread out so that there are no
large unpopulated spaces in the rectangle, nor any areas of extremely high
population density.

Then any straight line through the center would divide the city into two
equal population districts.  The shortest possible boundary, the
intersection of the x-axis with the interior of the rectangle, would
yield a feasible solution.

But any intrinsic solution based on the "real taxicab metric" would
necessarily respect the river as the natural boundary.

Forest