<div dir="ltr"><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small">Two types of spatial models:</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) Traditional: Place individual voters randomly in an N-dimensional space, compute the distance between each voter and each candidate to compute that voter's ballot.<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">2) Polytope: Kristofer's recent idea, implemented by me. Place candidates in space, compute their Voronoi cells, intersect them to get all the regions in space associated with each ballot, and compute their volumes.</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">The allure of (2) is the hope for higher precision at low cost because you are computing areas and volumes. Looking at their source codes, QHull seems to compute volumes exactly, but the Polytope library I'm using definitely computes volumes by random sampling. That might still be better than method (1) because the operations you do to compute a volume (linear inequalities) are simpler and easier to offload to a NumPy backend or even LAPACK than the sqrt() and if-branches that (1) requires. I want to benchmark this when I have time.</div><div class="gmail_default"><br></div><div class="gmail_default">The downside of (2) is that it forces you to assume that voters are spread out uniformly across the space. Only method (1) allows you to distribute voters according to some reasonable distribution like a Gaussian.</div><div class="gmail_default"><br></div><div class="gmail_default">I would like to present an idea for a third method that combines features of (1) and (2):</div><div class="gmail_default"><br></div><div class="gmail_default">3) Weighted Polytope: Compute Voronoi cells and their polytope intersections exactly as in (2). But instead of assuming that voters are uniformly distributed (i.e. Voters = Volumes), you also have a function like (1) that tells you the voter density in space. Your goal now is to integrate the voter density across the polytope associated with each ballot:</div><div class="gmail_default"><br></div><div class="gmail_default">Voters = Mass = Integral{ Density x Volume }</div><div class="gmail_default"><br></div><div class="gmail_default">We have to do the integral by random sampling, but that's what the Polytope library is doing anyway. Here is how Polytope computes volume:</div><div class="gmail_default"><br></div><div class="gmail_default">a) Draw random points from the smallest box that contains the polytope.</div><div class="gmail_default">b) Count the points that are inside the polytope (i.e. satisfy all the half-space inequalities).</div><div class="gmail_default">c) Volume = (Volume of box) * (Points inside) / (All points)</div><div class="gmail_default"><br></div><div class="gmail_default">To compute the "Mass" of the polytope with variable density, we just need to add two steps:</div><div class="gmail_default"><br></div><div class="gmail_default">d) For each point x inside the polytope, compute Density(x).</div><div class="gmail_default">c) Voters = Mass = Volume x (Mean Density)</div><div class="gmail_default"><br></div><div class="gmail_default">Step (d) can be done in NumPy, so I *hope* that this wouldn't be vastly more expensive than what the Polytope library already does. And as I noted earlier, I don't yet know whether computing volumes is actually faster than method (1) for comparable accuracy. But if it is, then my method (3) could be the best of both worlds:</div><div class="gmail_default"><br></div><div class="gmail_default">- The superior speed vs accuracy trade-off geometry (2).</div><div class="gmail_default">- The flexibility and realism of a dedicated voter-density function (1).</div><div class="gmail_default"><br></div><div class="gmail_default">It might be several days before I have time to experiment with this, but I wanted to put the ideas out there and see if any of you had any thoughts.</div><div class="gmail_default"><br></div><div class="gmail_default">Cheers,</div></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>