[EM] A computationally feasible method (algorithmic redistricting)

[Raph Frank]

On Tue, Sep 2, 2008 at 11:00 PM, Kristofer Munsterhjelm
<km-elmet at broadpark.no> wrote:
> 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 :-)

My splitline software used a sphere (and gnomonic projection for the
lines).  However, I think it wasn't necessary, but wanted it to be as
accurate as possible.

OTOH, I think that it might be better to define the map as a 2d map
using Mercator projection.  The problem with the sphere is that each
point is a real number.

If the data is presented as (longitude, latitude), then the numbers
that are input into the algorithm are rational numbers as they are
given with a certain number of digits after the decimal point.  This
allows an exact solution to be found.  However, with reals, different
precisions could give different answers.  Also, if there is a tie, it
may not be possible to determine that one occurs.  This is less of a
problem if a specific algorithm for determining the result is used.

I think splitline can be solved exactly if the map is 2-d and all
coordinates in the input data are rational numbers.

Back to to the Voronoi diagrams, I think you may have misunderstood
what I meant.

The issue here is that ordinarily, it doesn't matter what power you use.

If you colour each pixel the colour of the nearest point, then you get
a standard Voronoi  diagram.

Likewise, if you say that you colour each pixel the colour of the
point with the lowest (distance)^2, then you get the same diagram.

If you square all the distances, then the lowest distance is still the lowest.

All cells will have straight lines as their edges.

However, if I say that you should colour the pixel the colour of the
nearest point, but that the distance to point 1 is to be decreased by
100km, then you would expect that the cell with point 1 as its centre
would be increased in size as some pixels which went to other cells,
would now go to point 1's cell (as its distance has been decreased).

If you look at the results, then you would see that cell 1 no longer
has straight lines as its boundary.

Now, if instead, you assign the pixels to the cell with the nearest
distance squared and apply an offset to point 1, then you still
maintain straight line edges.

Also, it has the nice feature that you can work out the square distance as

(x0-x1)^2 + (y0-y1)^2 + Cn

You save a square root which takes a long time to calculate.

> 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

Cool, he also has the one I am talking about

http://www.nirarebakun.com/voro/epwvoro.html

The number beside each point is the weight

He also shows the result if you use distance instead of distance squared.

http://www.nirarebakun.com/voro/eawvoro.html

.. and weighting by multiplying

http://www.nirarebakun.com/voro/emwvoro.html

Actually, that site is pretty cool. :)

That last one might be ideal for districting.  It would allow a city
to be a circle which surrounded by a rural district.

For example, if you had a State with 2 cities and 3 seats, it might be
best to split the state into 2 circle districts centred on the cities
and 1 rural district which is everyone else.

Most other methods can't handle having one district as an island
contained in another.

> 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.

Yeah, most of the automatic methods assume that the 'population' is
uniform density.

What is nice about the reweighted version is that you can expand and
contract a region without having to move the points.

If you increase a region's weight, it gets smaller.

> 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).

Maybe both the Cd and the position of each point could be moved.

I think for (nearly) any given set of points, it is possible to create
a set of Cd values that will give near equal population.

The algorithm could be something like:

1) Pick initial points (some rule)
2) Determine set of Cds to give equal populations
3) Move points towards geographic centres of districts
4) goto 2) until points have converged

This probably doesn't always converge, so a method would need to be
created which always converges.

> 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 .

Yeah, though it isn't my generalization, Warren pointed it out to me.

> 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 only browsed the paper, just to find the definition of power diagram.

> 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.

Perhaps, they would have to beat the default map by some measure.

One option would be to say that at least 80% of the residents assigned
to a given district must also be assigned to that district after the
commission has refined the map to take into account whatever
aesthetics are appropriate.