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,
is Lloyd's algorithm. Start with random center points, then calculate
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.
----
Election-Methods mailing list - see http://electorama.com/em for list info
