[EM] connection of political districting to image-dithering problem

[Warren Smith]

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