<div dir="ltr"><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small">Hi guys,</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">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 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">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 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"><div class="gmail_default"><a href="http://www.qhull.org/">http://www.qhull.org/</a><br></div><div class="gmail_default"><a href="https://docs.scipy.org/doc//scipy/reference/generated/scipy.spatial.Voronoi.html">https://docs.scipy.org/doc//scipy/reference/generated/scipy.spatial.Voronoi.html</a><br></div></div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><a href="https://docs.scipy.org/doc//scipy/reference/generated/scipy.spatial.ConvexHull.html">https://docs.scipy.org/doc//scipy/reference/generated/scipy.spatial.ConvexHull.html</a><br></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">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 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) Start with your list of candidates / points and your bounding box.</div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small">2) Reflect the points along each side of the bounding box.</div><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small">3) Compute the Voronoi cells of *that*.</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">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 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"><a href="https://stackoverflow.com/questions/28665491/getting-a-bounded-polygon-coordinates-from-voronoi-cells">https://stackoverflow.com/questions/28665491/getting-a-bounded-polygon-coordinates-from-voronoi-cells</a><br></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">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 class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><br></div><div><div class="gmail_default" 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 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"><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" 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">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 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"><a href="https://stackoverflow.com/questions/70452216/how-to-find-the-intersection-of-2-convex-hulls">https://stackoverflow.com/questions/70452216/how-to-find-the-intersection-of-2-convex-hulls</a><br></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">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 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">Cheers,</div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="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>