<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><br></div></div><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Jan 27, 2022 at 4:20 AM Kristofer Munsterhjelm <<a href="mailto:km_elmet@t-online.de">km_elmet@t-online.de</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">> Finding the area of a Voronoi cell in a 2D space with just 3-4 cells<br>
> doesn't sound difficult. I haven't done the math, but it feels like high<br>
> school math problem.<br>
<br>
It isn't very difficult. Fortune's algorithm can get the cells in O(c<br>
log c) time, and then you can find the area of each (given its vertices)<br>
by sorting the vertices in a particular order, in O(v log v) time. IIRC,<br>
the number of vertices of a 2d Voronoi cell is bounded, so that is in<br>
essence constant time.<br>
<br>
A side note: I seem to recall that Patterns of Democracy (by Lijphart)<br>
says that as a reasonable approximation, the number of dimensions in a<br>
country's political realm is the number of effective parties, plus one.<br>
(And anecdotally there definitely seems to be more than one dimension to<br>
politics here.)<br></blockquote><div> </div><div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">You know, if we embrace the idea that the number of dimensions scales with the number of parties and make it part of the model, that simplifies the possible shapes of the 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">a) 3 candidates in a 2D space, as long as they don't fall on a line, must have Voronoi cells that all meet at a point.</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">b) 3 candidates in a 3D space, as long as they don't fall on a line, must have Voronoi cells that all meet at a line.</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">c) 3 candidates in a 4D space, as long as they don't fall on a line, must have Voronoi cells that all meet on a plane.</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">More generally, my intuition is that N candidates in a space with at least N-1 dimensions cannot "surround" each other and that limits the possible set of shapes their Voronoi cells can have. Furthermore, I suspect that if the space has exactly N-1 dimensions, the Voronoi cells probably all meet at a point and the cells look similar to triangles/pyramids/etc. They're not exactly triangles/pyramids because the one side of the cell ends at the boundary of the space and we haven't defined what shape that's going to have. Nonetheless, my point is that we don't need to compute the volume of a fully generic Voronoi cell in higher dimension; just a relatively simple subtype.</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></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>