On Tue, Sep 2, 2008 at 11:00 PM, Kristofer Munsterhjelm <[EMAIL PROTECTED]> 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. ---- Election-Methods mailing list - see http://electorama.com/em for list info
