[EM] Alternative algorithms for Yee diagrams.

[Kristofer Munsterhjelm]

On 12/12/2013 01:11 AM, Leon Smith wrote:
> Here's the result of a conversation I had with Claude Heiland-Allen
> today about faster algorithms for generating Yee Diagrams.
>
> http://mathr.co.uk/blog/2013-12-11_distance_estimation_for_voting_simulation_visualisation.html
>
> I haven't run any timing tests yet,  so it's not clear if this is faster
> as-is or not.   And there is probably substantial room for further
> improvement... e.g. in selecting starting points more intelligently.
>
> Also, the obvious generalization of this algorithm to ranked methods
> would also slow it down a bit.  But I thought it might be of interest to
> some people here on this list.

I once suggested a way of drawing a Yee diagram with more or less 
infinite precision by constructing ranked Voronoi maps (e.g. polygons 
where every voter in that polygon has a particular ranking), then 
calculating the "area" of the polygon in relation to a given center 
point by evaluating Gaussian integrals. The center point would be the 
pixel in question, so you'd have to evaluate a Gaussian integral for 
each polygon for each pixel.

If the distance estimator lets you fill in some pixels as obvious, then 
it could also be used to skip evaluating the integrals where the outcome 
is given. So the approaches may be complementary.

I haven't had the time to make proof of concept code for the idea, 
though, but a few days ago I think I saw that the C++ Boost library has 
Voronoi mapping functions as well as a polygon class. (Determining the 
ranked Voronoi regions would be a matter of recursing: first determine 
the ordinary Voronoi map, then determine the Voronoi map inside each 
polygon with the candidate already closest excluded, and so on.)

Still, it may be an idea to think about!