<div dir="auto"><div><br><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">El dom., 6 de feb. de 2022 3:00 p. m., Daniel Carrera <<a href="mailto:dcarrera@gmail.com">dcarrera@gmail.com</a>> escribió:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><span style="font-family:Arial,Helvetica,sans-serif">On Sun, Feb 6, 2022 at 4:13 PM Kristofer Munsterhjelm <<a href="mailto:km_elmet@t-online.de" target="_blank" rel="noreferrer">km_elmet@t-online.de</a>> wrote:</span><br></div></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Calculating the area of a simplex is pretty easy. The trouble is in the<br>
triangulation: the number of simplices for a fully general polytope can<br>
increase very quickly (superpolynomially) in the number of dimensions.<br>
That said, this is the approach some exact volume calculation methods<br>
use. I think<br>
<a href="https://link.springer.com/chapter/10.1007%2F978-3-0348-8438-9_6" rel="noreferrer noreferrer" target="_blank">https://link.springer.com/chapter/10.1007%2F978-3-0348-8438-9_6</a> has more<br>
information about such algorithms.<br>
<br>
If there's a proof that Voronoi polytopes only contain small number of<br>
simplices (preferably according to some triangulation algorithm), then<br>
all the better, of course! I'm not aware of any such, though. I think<br>
finding the minimal simplex triangulation is hard for a general<br>
polytope, though I'm not sure of that either.<br>
</blockquote></div><div><br></div><div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">This is my first time thinking about computational geometry, but it seems to me that even if you are unlucky, the number of simplices should only grow linearly with the number of candidates. I have no idea how to find the minimal simplex triangulation for a general polytope, but for the special case of a convex hull, like a Voronoi cell, it doesn't look super hard:</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) Let C be a convex hull with > N+1 vertices in N dimensions.</div></div></div></blockquote></div></div><div dir="auto"><br></div><div dir="auto"></div><div dir="auto">Recursively triangulate the boundary of C into a union beta of (N-1) dim'l simplices.</div><div dir="auto">Then let p be any point of the interior of C, and cone every member of beta over p. Then C is the union of the resulting N dimensional simplices.</div><div dir="auto"><br></div><div dir="auto"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><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) Select a random set of N vertices from C.</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) Find the equation for the hyper-plane that goes through those vertices. Those equations have the form:</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">Sum{ a_k * x_k } = b</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">Without loss of generality, let `b=1`. We have N points that satisfy the equation. That gives a linear system `X*{a} = {1}` where the rows of X are the N vertices, and {a} and {1} are vectors.</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">4) The equations</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">Sum{ a_k * x_k } > 1<br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">Sum{ a_k * x_k } < 1<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">Split C into two polytopes that are also convex hulls.</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">5) Repeat for each sub-polytope. Stop when the sub-polytope is a simplex.</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"><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>
----<br>
Election-Methods mailing list - see <a href="https://electorama.com/em" rel="noreferrer noreferrer" target="_blank">https://electorama.com/em</a> for list info<br>
</blockquote></div></div></div>