Exact Volume Computation for Polytopes: A Practical Study
Benno Büeler, Andreas Enge, Komei Fukuda · Birkhäuser Basel eBooks · 2000
We study several known volume computation algorithms for convex d-polytopes by classifying them into two classes, triangulation methods and signed-decomposition methods. By incorporating the detection of simplicial faces and a storing/reusing scheme for face volumes we propose practical and theoretical improvements for two of the algorithms. Finally we present a hybrid method combining advantages from the two algorithmic classes. The behaviour of the algorithms is theoretically analysed for hypercubes and practically tested on a wide range of polytopes, where the new hybrid method proves to be superior. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.