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

[Daniel Carrera]

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.

http://www.qhull.org/
https://docs.scipy.org/doc//scipy/reference/generated/scipy.spatial.Voronoi.html
https://docs.scipy.org/doc//scipy/reference/generated/scipy.spatial.ConvexHull.html

The next problem that I ran into is that most of the Voronoi cells have an
infinite volume because they are unbounded. I could not find any way to
define a bounding box to "clip" the Voronoi cells. One poster on
StackOverflow suggested a solution:

1) Start with your list of candidates / points and your bounding box.
2) Reflect the points along each side of the bounding box.
3) Compute the Voronoi cells of *that*.

Reflecting points along each side of the box forces the Voronoi cells that
you care about to actually stop at the walls of the box exactly. You can
later filter out all the cells outside the bounding box to get the ones you
really need.

https://stackoverflow.com/questions/28665491/getting-a-bounded-polygon-coordinates-from-voronoi-cells

Ok. So now you can figure out what fraction of voters will select candidate
'A' first. But that was only step one. What we really want to do is compute
Voronoi cells and volumes many times with different lists of candidates to
gradually work out the entire ballots. For example, save the Voronoi cell
for 'A'-voters, remove 'A'  and re-run the Voronoi cell calculator. So now
the 'A'-voters will be in different cells. Compute the intersection of
every cell with the old 'A'-voters cell and you now have the 'A>B'-cell,
the 'A>C'-cell and so on.

The only problem? The library doesn't have an obvious way to take the
intersection of two convex hulls. What it does have is a way to define a
shape as the intersection of multiple half-spaces.

https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.HalfspaceIntersection.html

But I can't figure out how to use this to intersect two convex hulls. You'd
think that it would be doable, and that someone should have solved this
problem already but I could not find a solution. Someone asked this on
StackOverflow and they were pointed to yet another library:

https://stackoverflow.com/questions/70452216/how-to-find-the-intersection-of-2-convex-hulls

At this point everything is looking harder than it needs to be, and I
couldn't go any further. Does anyone either know how to use scipy.spatial
or know of an entirely different toolkit that can take intersections of
Voronoi cells?

Cheers,
-- 
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220129/d63453de/attachment-0001.html>