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 Ω.

REFERENCES

• 1: BARVINOK, A. I. 1993. Computing the volume, couting integral points and exponentials sums, Discr. Comput. Geom. 10, 123-141.
• 2: BRYCHKOY, Y. A., GLAESKE, H. J., PRUDNIKOY,A.P.,AND TUAN, V. K. 1992. Multidimensional Integral Transformations. Gordon and Breach, Philadelphia, Pa.
• 3: BUELER, B., ENGE, A., AND FUKUDA, K. 2000. Exact volume computation for polytopes: A practical study. In: Polytopes-Combinatorics and Computation, G. Kalai, and G. M. Ziegler, Eds., Birhauser Verlag, Basel.
• 4: Jacques Cohen , Timothy Hickey, Two Algorithms for Determining Volumes of Convex Polyhedra, Journal of the ACM (JACM), v.26 n.3, p.401-414, july 1979 [doi>10.1145/322139.322141]
• 5: CONWAY, J. B. 1978. Functions of a Complex Variable I, 2nd ed. Springer, New York.
• 6: DYER, M. E. 1983. The complexity of vertex enumeration methods. Math. Oper. Res. 8, 381-402.
• 7: M. E. Dyer , A. M. Frieze, On the complexity of computing the volume of a polyhedron, SIAM Journal on Computing, v.17 n.5, p.967-974, October 1988 [doi>10.1137/0217060]
• 8: GRITZMANN,P.,AND KLEE, V. 1994. Basic problems in computational convexity II. In Polytopes: Abstract; Convex and Computational, T. Bisztriczky, P. McMullen, R. Schneider, and A. I. Weiss, Eds. NATO ASI series, Kluwer Academic Publishers, Dordrecht.
• 9: HIRIART-URRUTY, J.-B., AND LEMARECHAL, C. 1993. Convex Analysis and Minimization Algorithms I. Springer-Verlag, Berlin, Germany.
• 10: LASSERRE, J. B. 1983. An analytical expression and an algorithm for the volume of a convex polyhedron in Rn. J. Optim. Theor. Appl. 39, 363-377.
• 11: LAWRENCE, J. 1991. Polytope volume computation, Math. Comput. 57, 259-271.
• 12: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 13: VON HOHENBALKEN, B. 1987. Finding simplicial subdivisions of polytopes, Math. Prog. 21, 233-234.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

General Terms:
Algorithms

Keywords:
Computational geometry, Laplace transform, convex polytopes, volume of a convex polytope