A Laplace transform algorithm for the volume of a convex polytope

Abstract

We provide two algorithms for computing the volume of the convex polytope Ω : = { x ∈ ℝ ⁿ ₊ | Ax ≤ b }, for A , ∈ ℝ ^{m × n} , b ∈ ℝ ⁿ . The computational complexity of both algorithms is essentially described by n ^m , which makes them especially attractive for large n and relatively small m , when the other methods with O ( m ⁿ ) complexity fail. The methodology, which differs from previous existing methods, uses a Laplace transform technique that is well suited to the half-space representation of Ω.