[EM] Fast algorithms for Yee/Bolson pictures

[Warren Smith]

Concerning those pictures by Ka-Ping Yee and Brian Olson.

The naive method of producing these pictures, assuming an NxN pixel picture
and V voters per election, takes time of order (N*N*V).

I just want to point out for algorithms fans,
that it is possible to accomplish essentially
the same thing, and in the V=infinity limit too,
in time of order
    O(N*N*logN).

The idea is, for each pixel=election, to determine the percentages 
of each kind of vote (there are only a constant number of kinds of votes
in rank-order election methods or approval), by performing a fast convolution
with the Gaussian, using an FFT.  With these percentages
all determined, the elections thmselves may then be done in
constant time each.

For range voting or any additive method, we do not determine the
percentages of different vote types; we instead directly determine the
election totals via fast convolutions.

If you enjoy having V finite instead of infinite, then that effect can be got
by adding random noise to the vote-percentage totals got from the fast convolution,
with the random noise amplitudes appropriately chosen.  The runtime
is O(N*N*logN) independent of V.

With N=200 and V=200,000  (Yee) I estimate the time savings
should be a factor of at least 1,000.

Warren D. Smith
http:/rangevoting.org