<div dir="ltr"><div dir="ltr"><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 Mon, Feb 7, 2022 at 12:16 PM Forest Simmons <<a href="mailto:forest.simmons21@gmail.com">forest.simmons21@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="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" target="_blank">dcarrera@gmail.com</a>> escribió:<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 dir="ltr"><div 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" rel="noreferrer" target="_blank">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 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 style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div 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>
</blockquote></div><div><br></div><div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">I'm pretty new to the field, but that sounds like it should work. I can't imagine how it wouldn't. I can already get a list of vertices from the Polytope library and I can give those to QHull (via scipy.spatial) and QHull can give me a list of simplices that make up the faces. Lastly, to get p we can grab any two vertices that do not share a face and pick the midpoint. It's hard to see how that could go wrong, but then again, what do I know?</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"></div></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">Kristofer pointed out that my previous algorithm wouldn't work efficiently in cases where most sets of N+1 vertices share a face (e.g. a square base pyramid in 3D). But your idea has no such problem as far as I can tell. I'm sure that the general problem of dividing up a polytope into simplices is very hard, but the specific case of a Voronoi cell honestly looks easy.</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">If there is a reason why it is better to divide the Voronoi cell into as few simplices as possible, a variation of my algorithm could work well. Instead of grabbing vertices at random you'd have to do something more clever to avoid grabbing vertices that don't all share the same face, but that doesn't sound 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">Cheers,</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>