[EM] Exact volume of a simplex

[Forest Simmons]

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.


> 2) Select a random set of N vertices from C.
>
> 3) Find the equation for the hyper-plane that goes through those vertices.
> Those equations have the form:
>
> Sum{ a_k * x_k } = b
>
> 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.
>
> 4) The equations
>
> Sum{ a_k * x_k } > 1
> Sum{ a_k * x_k } < 1
>
> Split C into two polytopes that are also convex hulls.
>
> 5) Repeat for each sub-polytope. Stop when the sub-polytope is a simplex.
>
> Cheers,
> --
> Dr. Daniel Carrera
> Postdoctoral Research Associate
> Iowa State University
> ----
> Election-Methods mailing list - see https://electorama.com/em for list
> info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220207/e813e844/attachment.html>