Estimate Volumes of Convex Polytopes: A New Method Based on Particle Swarm Optimization
Sheng Hui Xu, Dun Bo Cai · Advanced materials research · 2014
The volume of a convex polytope is important for many applications, and generally #P-hard to compute. In many scenarios, an approximate value of the volume is sufficed to utilize. Existing methods for estimating the volumes were mostly based on the Monte Carlo algorithm or its variants, which required a near uniform sampling process with a large number of sample points. In this paper, we propose a new method to estimate the volumes of convex polytopes that needs relative less sample points. Our method firstly searches for fringe points that are inside and near the border of a convex polytope, by a new way of utilizing the particle swarm optimization (PSO) technique. Then, the set of fringe points is input to a tool called Qhull whose output value serves as an estimate of the real volume. Experimental results show that our method is efficient and gives result with high accuracy for many instances of 10-dimension and beyond.