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

[Kristofer Munsterhjelm]

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