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

[Daniel Carrera]

Some additional thoughts:

1) The scipy.spatial.HalfspaceIntersection defines a convex hull as an
intersection of half-spaces. If we can express the Voronoi cells this way,
then intersections are potentially very easy. The intersection of two
volumes defined by a list of half-space inequalities is just stacking all
the inequalities.

HOWEVER...

2) I'm not yet sure how to convert a scipy.spatial.Voronoi cell into a
bunch of inequalities.

3) The function also asks for an interior point. I don't really know how to
get one, but the documentation says "it can be obtained by linear
programming." --- so maybe this is a problem that someone that works with
MIPS knows how to solve. For the first Voroni space, the candidate is
obviously an interior point. But once you start taking intersections, I
don't really know what to do.

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


Cheers,
Daniel


On Sat, Jan 29, 2022 at 1:35 PM Daniel Carrera <dcarrera at gmail.com> 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.
>
> 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
>


-- 
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/7335ed40/attachment.html>