[EM] Exact volume of a simplex

[Kristofer Munsterhjelm]

On 06.02.2022 20:30, Daniel Carrera wrote:
> It turns out that computing the volume of a simplex is surprisingly easy:
> 
> https://www.mathpages.com/home/kmath664/kmath664.htm
> <https://www.mathpages.com/home/kmath664/kmath664.htm>
> 
> Let {vk} for k=0...{N+1} be the N+1 vectors that make the vertices of
> the N-simplex.
> 
> Let B be the (N+1)x(N+1) matrix whose rows are `1` followed by the
> elements of {vk}.
> 
> The volume of the simplex is:
> 
> Volume = det(B) / N!
> 
> This is so easy, I don't understand why the Polytope library doesn't do
> it this way. In any case, this means that Kristofer's original idea of
> computing the volumes of polytopes exactly and using that as your
> spatial model should be computationally efficient. You just have to
> split your Voronoi cells into simplices, which isn't too hard either.

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.

-km