<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small">Some additional thoughts:</div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small">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.</div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small">HOWEVER...</div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small">2) I'm not yet sure how to convert a scipy.spatial.Voronoi cell into a bunch of inequalities.</div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small">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.</div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><div class="gmail_default"><br class="gmail-Apple-interchange-newline"><a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.HalfspaceIntersection.html">https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.HalfspaceIntersection.html</a><br></div><div class="gmail_default"><br></div><div class="gmail_default"><br></div></div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small">Cheers,</div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small">Daniel</div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sat, Jan 29, 2022 at 1:35 PM Daniel Carrera <<a href="mailto:dcarrera@gmail.com">dcarrera@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div style="font-family:"trebuchet ms",sans-serif;font-size:small">Hi guys,</div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><div><a href="http://www.qhull.org/" target="_blank">http://www.qhull.org/</a><br></div><div><a href="https://docs.scipy.org/doc//scipy/reference/generated/scipy.spatial.Voronoi.html" target="_blank">https://docs.scipy.org/doc//scipy/reference/generated/scipy.spatial.Voronoi.html</a><br></div></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><a href="https://docs.scipy.org/doc//scipy/reference/generated/scipy.spatial.ConvexHull.html" target="_blank">https://docs.scipy.org/doc//scipy/reference/generated/scipy.spatial.ConvexHull.html</a><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small">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:</div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small">1) Start with your list of candidates / points and your bounding box.</div><div style="font-family:"trebuchet ms",sans-serif;font-size:small">2) Reflect the points along each side of the bounding box.</div><div style="font-family:"trebuchet ms",sans-serif;font-size:small">3) Compute the Voronoi cells of *that*.</div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><a href="https://stackoverflow.com/questions/28665491/getting-a-bounded-polygon-coordinates-from-voronoi-cells" target="_blank">https://stackoverflow.com/questions/28665491/getting-a-bounded-polygon-coordinates-from-voronoi-cells</a><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div><div style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.HalfspaceIntersection.html" target="_blank">https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.HalfspaceIntersection.html</a><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small">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:</div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><a href="https://stackoverflow.com/questions/70452216/how-to-find-the-intersection-of-2-convex-hulls" target="_blank">https://stackoverflow.com/questions/70452216/how-to-find-the-intersection-of-2-convex-hulls</a><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small">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?</div></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div style="font-family:"trebuchet ms",sans-serif;font-size:small">Cheers,</div>-- <br><div dir="ltr"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><font face="trebuchet ms, sans-serif">Dr. Daniel Carrera</font></div><div dir="ltr"><font face="trebuchet ms, sans-serif">Postdoctoral Research Associate</font></div><div><font face="trebuchet ms, sans-serif">Iowa State University</font></div></div></div></div></div></div></div></div></div></div></div>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><font face="trebuchet ms, sans-serif">Dr. Daniel Carrera</font></div><div dir="ltr"><font face="trebuchet ms, sans-serif">Postdoctoral Research Associate</font></div><div><font face="trebuchet ms, sans-serif">Iowa State University</font></div></div></div></div></div></div></div></div></div></div></div>