The "image dithering" problem is this. You are given a continuous-tone greyscale image. You wish to convert it into a pure black and white image that "looks the same" so you can print it on a pure black and white printer.
This is almost the same problem as the political districting problem: change "grey level" to "population density" and "black dot" to "district representative." Hence it is possible to adapt known algorithms for image dithering, to work for political districting purposes. One of the emprically-best dithering algorithms was invented by R.W. Floyd & L.Steinberg: An adaptive algorithm for spatial grey scale, Proceedings of the Society of Information Display 17 (1976) 75-77. J.F.Jarvis, C.N.Judice, W.H.Ninke: A survey of techniques for the display of continuous tone pictures on bilevel displays, Computer Graphics and Image Processing, 5,1 (1976) 13-40. See http://en.wikipedia.org/wiki/Floyd-Steinberg_dithering . Here is how to turn it into a political districting algorithm, 1. input the locations of all the P people in the country. 2. "pixelize" that into an "image" by making a grid of boxes (each is a pixel) and encoding each box with its population (i.e. "grey level"). [One could also consider a "beehive" pattern of hexagonal boxes instead of square, which would probably work slightly better if the right kernel designs were used in step 4 below.] 3. Raster scan the image, i.e. traversing the boxes left to right on each row, then moving the row vertically downward. 4. As we scan, move the current box's population to its neighboring boxes according to the Floyd-Steinberg kernel: (.....0...x...7) (.....3...5...1) / 16 which means that the population in the pixel labeled "x" is transferred to its East, SW, S, and SE neighbors in fractions 7/16, 3/16, 5/16, and 1/16. Or you could use the JaJuNi kernel instead: (....0...0...x...7...5) (....3...5...7...5...3) (....1...3...5...3...1) / 48 If we were instead using hexagonal-beehive pixels, a natural analogue of the JaJuNi kernel might be (....0...0...x...3...1) (.0...2...3...3...2...) (....0...1...2...1...0) / 18 but I am not claiming this is best. 5. Every time a pixel-box is encountered which contains more than some threshold T of population, label that box ("with a black dot") as a "district center"; then only transfer (using the Floyd-Steinberg or JaJuNi kernel) the part of its population ABOVE that threshold. The threshold T needs to be chosen so that we get the right number of districts, i.e. if you want N districts use T=P/N. This algorithm tends to move district centers downward and rightward from where they really ought to be, but seems to work pretty well aside from that. It is possible to remove this southern+eastern bias by instead placing the "dot" at the mean-location of all the population responsible for it. To do that, you'd also need to keep track of (and transfer) not only population counts, but also sums of x and sums of y coordinates, for the homes of all the people currently in each pixel. This is an extremely fast and simple algorithm, running in O(P) time for P people if a grid with O(P) boxes is used. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step) and math.temple.edu/~wds/homepage/works.html ---- Election-Methods mailing list - see http://electorama.com/em for list info
