A new algorithm for the volume of a convex polytope

2001/06/20 by Jean B. Lasserre, Lasserre, J. B., E. S. Zeron +1
Computer Science · Mathematics · #26B15 (Primary) 51M25 #51M20 #52B11 (Secondary) #Advanced Optimization Algorithms Research #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics #Numerical Analysis (math.NA)

paper · pdf · doi:10.48550/arxiv.math/0106168

openalex publication_date 2001/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We provide two algorithms for computing the volume of a convex polytope with half-space representation x>=0; Ax <=b for some (m,n) matrix A and some m-vector b. Both algorithms have a O(n^m) computational complexity 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 the polytope.

Related

• Unmixing the mixed volume computation
• An FPTAS for the Volume of a \cal V-polytope ---It is Hard to Compute The Volume of The Intersection of Two Cross-polytopes
• Computing the Volume of Polytropes
• Volume of convex polytopes equals mixed volume of simplices
• Approximating mixed volumes to arbitrary accuracy