[EM] Exact volume of a simplex

[Forest Simmons]

If you are looking for minimal number of simplices in the triangulation of
an intersection of half spaces (like the feasible region of a linear
programming problem) ... it really isn't necessary to introduce new
vertices like p in the interior of a  existing convex cell ... that was
just a convenience to shorten the explanation.

For example, think of a convex polygon in a plane ... just cone the edges
from one of the existing vertices. Some of those cones will not be top
dimensional, like the cones over the two edges incident to the cone vertex,
so just throw them out or ignore them.

El lun., 7 de feb. de 2022 4:17 p. m., Daniel Carrera <dcarrera at gmail.com>
escribió:

>
>
> 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/70cc0736/attachment.html>