[EM] Exact volume of a simplex

[Daniel Carrera]

On Mon, Feb 7, 2022 at 12:16 PM Forest Simmons <forest.simmons21 at gmail.com>
wrote:

>
>
> El dom., 6 de feb. de 2022 3:00 p. m., Daniel Carrera <dcarrera at gmail.com>
> escribió:
>
>> On Sun, Feb 6, 2022 at 4:13 PM Kristofer Munsterhjelm <
>> km_elmet at t-online.de> wrote:
>>
>>> Calculating the area of a simplex is pretty easy. The trouble is in the
>>> triangulation: the number of simplices for a fully general polytope can
>>> increase very quickly (superpolynomially) in the number of dimensions.
>>> That said, this is the approach some exact volume calculation methods
>>> use. I think
>>> https://link.springer.com/chapter/10.1007%2F978-3-0348-8438-9_6 has more
>>> information about such algorithms.
>>>
>>> If there's a proof that Voronoi polytopes only contain small number of
>>> simplices (preferably according to some triangulation algorithm), then
>>> all the better, of course! I'm not aware of any such, though. I think
>>> finding the minimal simplex triangulation is hard for a general
>>> polytope, though I'm not sure of that either.
>>>
>>
>> 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:
>>
>> 1) Let C be a convex hull with > N+1 vertices in N dimensions.
>>
>
> Recursively triangulate the boundary of C into a union beta of (N-1) dim'l
> simplices.
> 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.
>

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?
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.

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.

Cheers,
-- 
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220207/3cd9f283/attachment.html>