A Fast and Practical Method to Estimate Volumes of Convex Polytopes

DOI10.1007/978-3-319-19647-3_6MaRDI QIDQ3452552zbMATH OpenOpenAlexFDO

Authors Cunjing Ge, Feifei Ma

Publication date 12 November 2015

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.0120

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: The volume is an important attribute of a convex body. In general, it is quite difficult to calculate the exact volume. But in many cases, it suffices to have an approximate value. Volume estimation methods for convex bodies have been extensively studied in theory, however, there is still a lack of practical implementations of such methods. In this paper, we present an efficient method which is based on the Multiphase Monte-Carlo algorithm to estimate volumes of convex polytopes. It uses the coordinate directions hit-and-run method, and employs a technique of reutilizing sample points. The experiments show that our method can efficiently handle instances with dozens of dimensions with high accuracy.

Recommendations

• scientific article; zbMATH DE number 683230
• Practical polytope volume approximation
• scientific article; zbMATH DE number 1538124
• Approximating the volume of convex bodies
• scientific article; zbMATH DE number 17646
• Volume approximation of convex bodies by inscribed polytopes
• scientific article; zbMATH DE number 597730
• Efficient random-walk methods for approximating polytope volume
• A random polynomial-time algorithm for approximating the volume of convex bodies
• An Efficient Algorithm for Obtaining the Volume of a Special Kind of Pyramid and Application to Convex Polyhedra

Cites work

• Computational results of an \(O^{\ast }(n^{4})\) volume algorithm
• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• Geometric algorithms and combinatorial optimization.
• Hit-and-Run Algorithms for Generating Multivariate Distributions
• Hit-and-run algorithms for the identification of nonredundant linear inequalities
• Hit-and-run mixes fast
• scientific article; zbMATH DE number 4108152 (Why is no real title available?)
• scientific article; zbMATH DE number 1538124 (Why is no real title available?)
• Modifications and implementation of the ellipsoid algorithm for linear programming
• On the Complexity of Computing the Volume of a Polyhedron
• Random walks and anO*(n5) volume algorithm for convex bodies
• Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
• Volume Computation Using a Direct Monte Carlo Method

Cited in

(15)

• Computing and estimating the volume of the solution space of SMT(LA) constraints
• Practical volume approximation of high-dimensional convex bodies, applied to modeling portfolio dependencies and financial crises
• On the sample-mean method for computing hyper-volumes
• Fast algorithms for the minimum volume estimator
• A practical volume algorithm
• Unbiased estimation of the volume of a convex body
• Volume Computation Using a Direct Monte Carlo Method
• scientific article; zbMATH DE number 1538124 (Why is no real title available?)
• Practical polytope volume approximation
• Practical volume estimation of zonotopes by a new annealing schedule for cooling convex bodies
• scientific article; zbMATH DE number 7236423 (Why is no real title available?)
• Deterministic and stochastic methods for computing volumetric moduli of convex cones
• An algorithm for estimating non-convex volumes and other integrals in \(n\) dimensions
• A practical algorithm for volume estimation based on billiard trajectories and simulated annealing
• Monte-Carlo integration on a union of polytopes

This page was built for publication: A Fast and Practical Method to Estimate Volumes of Convex Polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452552)