Raph Frank wrote:
On 9/2/08, Brian Olson <[EMAIL PROTECTED]> wrote:
I have implemented essentially that, and it pretty quickly gets pretty good
results as measured by the "distance per person to land-area-center" test. I
added one thing to deal with variations in population density. Each district
center also has an associated weight. Each 'voronoi cell'/district contains
the people with a weighted distance closest to that district center. So, a
district center in a high population density area doesn't have to reach very
far to gather its allotment of people.
Your maps don't look like voronoi diagrams (edges aren't lines).
Do you assign based on
Assign voter to district with minimum
distance to district centre - Cd
Where Cd is some coefficient for the district d. Cd is set so as to
give equal populations.
If so, have you considered using squared distance instead of distance?
Assign voter to district with min
(distance to centre)^2 - Cd
This gives straight district edges (I think).
You might need to change your rule to
The best district map is the one where people have the lowest average
*squared* distance to the center of their district.
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 :-)
Euclidean distance is simply, sqrt((x1-x2)^2 + (y1-y2)^2) for 2D. Since
the Voronoi check would simply have to compare distances
(nearest-neighbor), and the square root function is monotonic, one can
cut it out to get (x1-x2)^2 + (y1-y2)^2.
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
I may appear to be agreeing with you here, but the point of this
explanation is to show that I don't think the artifacts you're seeing is
from him using Manhattan distance. In order to get curved results, you
have to go to at least the L3 distance of (|x1-x2|^3 + |y1-y2|^3)^(1/3).
That's a fairly strange metric, so I'm not sure why he gets curved
district borders.
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.
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).
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 . 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 think it's worth repeating that I'd prefer to write the law with a way of
measuring what a good district mapping is, rather than writing the law with
a specific procedure for creating the district mapping. Specific procedures
get really complex, and I don't think in this case that a fair procedure
ensures a fair outcome.
Sounds reasonable. However, people don't really like randomness.
There is considerable resistance to using randomness in elections and
people might consider a system where the solution isn't well defined
as somewhat random.
"You mean that the best solution mightn't be picked because nobody
could find it?"
Also, there could be issues if a better solution is found after the
deadline, especially, if it favoured one party over another.
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.
----
Election-Methods mailing list - see http://electorama.com/em for list info
