[EM] Exact volume of a simplex

[Daniel Carrera]

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.

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220206/0a7249a9/attachment.html>