[EM] Voronoi cells in Python? --- Exact spatial model

[Forest Simmons]

How about this approach:

Working by unions instead of intersections.

For working out the bugs, start with N=20 points randomly sampled from the
standard unit cube [0, 1]^3, with sufficiently many digits of precision to
avoid ties in what follows.

1.First assume, every point represents both a voter and a candidate.

Find each voter's ranking of all N candidates.  With enough precision and
randomness in the random number generator, the rankings will be strict and
complete.

N(N-1)/2 pairwise distance calculations, followed by N sorts to find each
voter/candidate's preference order.

2. Now suppose we want to consider a subset K of the original set kappa of
N candidates.

This can be accomplished by withdrawing the candidates of
 (kappa-K) one by one, adjusting the voter rankings of the remaining
candidates, as in any elimination method.

This results in a set of factions distributed among the remaining winners.

3. Find the winners of various methods, etc

4. To get another ballot set, assign different weights to the initial N
points, and go back to step 2.

If K is kept the same, the factions will not change, except for their
weights.


Change K from time to time, and eventually go all of the way back to step 1.





El sáb., 29 de ene. de 2022 3:21 p. m., Kristofer Munsterhjelm <
km_elmet at t-online.de> escribió:

> On 29.01.2022 20:35, Daniel Carrera wrote:
> > Hi guys,
> >
> > I like Kristofer's idea of using geometry and volumes to model elections
> > with essentially an infinite number of voters. Unfortunately I've never
> > really worked with computational geometry in any form, so I'm not really
> > familiar with the tools and techniques. I found a software library that
> > might have the tools required to implement Kristofer's idea, but I can't
> > quite figure out how to make it work.
> >
> > The scipy.spatial module is a Python front-end for the QHull library. If
> > you give it a set of points in N dimensions it will compute the Voronoi
> > cells and give you its vertices. You can convert the vertices into a
> > convex hull, and it can compute the volume of a convex hull.
>
> I haven't investigated QHull in detail, but as far as I know convex
> polytopes are usually represented (mathematically) in one of two ways:
> as a number of vertices (the vertex representation) or as a number of
> linear inequalities that all have to be satisfied (the half-space
> representation).
>
> The bad news is that going from one representation to another can be
> pretty costly. See https://mathoverflow.net/a/112441. Then again, so is
> determining the volume of a c.p., yet QHull can do that in practice.
>
> I'm surprised that QHull doesn't support facet enumeration, though.
>
> The obvious way to do limit Voronoi cells would be to intersect them
> with the box that covers the bounds of issue space... but you'd need
> intersection functionality to do that, too.
>
> -km
> ----
> Election-Methods mailing list - see https://electorama.com/em for list
> info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220129/c835af94/attachment.html>