[EM] High precision Yee diagrams

[Leon Smith]

On Sat, Jan 22, 2011 at 5:44 PM, Kristofer Munsterhjelm
<km-elmet at broadpark.no> wrote:
> This leaves the first step. At first glance, that seems to be prohibitive.
> If we have n candidates, there are n! possible ways to rank them, and so one
> would think that the combinatorial explosion would make the algorithm
> completely impractical. I thought so, too, but it seems that dimensionality
> significantly limits the explosion. For instance, if there are regions
> belonging to candidates A, B, and C, so that the distance from a given point
> in A to the closest point in C is always greater than the distance from that
> point to the closest point in B, then there can be no "A > C > B" voters in
> the A region (or at all, for that matter).
> Though I think it's possible to contrive examples where the number of
> distinct ballots grow superpolynomially with respect to the number of
> candidates, I think such examples will be unlikely in practice. I have no
> proof either way, though, but if any of you have, go ahead and mention it
> :-)

In the 2-d case,  the number of distinct ballots is,  at most, O(n^4)
in the number of candidates.  Given any pair of candidates,  a  voter
will rank one over the other based on which side of the perpendicular
bisector of the line segment between those two candidates.    There
are
m = n * (n-1) / 2 such lines,   which will split the plane into (at
most)   m * (m + 1) / 2 + 1  regions in which every voter will vote
the same.

http://oeis.org/A000124

Of course, this is with the standard voter model that everybody seems
to be using;  the numbers will change if you allow voters to rank
candidates equal when the distance from each candidate is sufficiently
similar.

Best,
Leon