Motivation: given the polytope in the form of linear equalities, computing its volume exactly or approximately.
Triangulation Method (Cohen and Hickey, 1979)
Main idea: dividing polytope into simplices and sum up the volumes of the resulting simplices.
Random-Walk Method (Ioannis Z. Emiris and Vissarion Fisikopoulos, 2018)
Main procedures:
- Hit-and-run random walk, which generates a uniform distribution of points in convex body
- Rounding and sandwiching polytope, which is finding the smallest enclosed ellipsoid
- Multiphase Monte Carlo: approximating polytope volume by telescopic product