[EM] A computationally feasible method (algorithmic redistricting)

Mon Sep 1 04:28:20 PDT 2008

```Michael Rouse wrote:
>
> There was a discussion of district-drawing algorithms on the
> election-methods list a few years back. I've always thought that taking
> centroidal Voronoi cells with equal populations was an elegant way to do
> it. Here's an example of standard Voronoi cells and the centroidal
> version I pulled off of Google:
> http://www.mrl.nyu.edu/~ajsecord/npar2002/html/stipples-node2.html

To find the district centers (centroids), you have to do what's
effectively vector quantization. The voters make up the points, and you
want to choose n codebook points so that the average distance to the
closest codebook point, for all points, is minimized.

To my knowledge, optimal vector quantization is NP-hard. The good news
is that there are approximation methods that have proven worst-case time
complexity. However, they'll not give you the absolutely best possible
arrangement.

One such algorithm is described here:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.3529

A simpler algorithm, though one that doesn't give any worst-case bounds,
the centroids for the current Voronoi cells. Move the center points
towards the centroid (shifting the Voronoi cell somewhat) and repeat. Do
so until they settle. This can get stuck in a local optimum.

> The other possibility I liked was allowing voters to vote for the
> districts they wanted -- either for the next election, or more
> entertainingly, the current one. People have a pretty good feel for what
> mapping is compact and reasonable, and which ones are ridiculous,
> especially if they can compare them. You could have certain criteria
> that must be met -- like all districts must be contiguous  -- and sort
> the maps by some metric, like from shortest to longest aggregate
> perimeter. You could have all qualifying parties submit a map, as well
> as any group that gets above a certain number of signatures in a petition.

Those maps could be pruned so that only the Pareto front remains. That
is, if there's some map that's worse on all metrics with regards to some
other map, then that first map isn't included. As long as there are
enough metrics to give a reasonable choice on the Pareto front, this
should exclude the worst of the gerrymandered proposals and keep the
voters from being swamped with millions of frivolous proposals.

I don't think it's necessary to make it that complex, though. If you
favor actual people doing the final choice, an independent commission
(like the redistribution commissions of Canada and Australia) could make
the choice of which nondominated map to use.

```