Estimate Volumes of Convex Polytopes: A New Method Based on Particle Swarm Optimization

Sheng Xu; Dun Bo Cai

doi:10.4028/www.scientific.net/AMR.1022.357

Paper Titles

Technology Study on the Perception of Stereopsis in Fovea Field
p.341

Research on the Monitoring of Internet with Public Opinions Based on Micro-Blog in Universities
p.345

The Teaching Web-Site Building of Technician Certificate for Electronic Elements Soldering and Taking Apart
p.349

Research on Information Technology in Effective Class Activities with Effective Class Measures
p.353

Estimate Volumes of Convex Polytopes: A New Method Based on Particle Swarm Optimization
p.357

Intelligent Optimization of Optimal Operating Mode in the Production Process of Copper Converter
p.361

Design and Implementation of an Encryption/Decryption System Based on FPGA
p.368

Numerical Investigation on Unsteady Flow Field of the Forward-Facing Cavity and Opposing Jet Combine Thermal Protection System
p.372

Research on the Ecological Water Demand Based on Physical Habitat Simulation Model
p.376

HomeAdvanced Materials ResearchAdvanced Materials Research Vol. 1022Estimate Volumes of Convex Polytopes: A New Method...

Estimate Volumes of Convex Polytopes: A New Method Based on Particle Swarm Optimization

Abstract:

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.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volume 1022)

Pages:

357-360

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.1022.357

Citation:

Cite this paper

Online since:

August 2014

Authors:

Sheng Xu, Dun Bo Cai*

Keywords:

Convex Polytope, Particle Swarm Optimization (PSO), Volume Estimation

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] M. E. Dyer, and A. M. Frieze: SIAM Journal on Computing Vol. 17(5) (1988), pp.967-974.

Google Scholar

[2] F. Bacchus, S. Dalmao, and T. Pitassi, in: Proc. of 44th Annual IEEE Symposium on Foundations of Computer Science, (2003).

DOI: 10.1109/sfcs.2003.1238208

Google Scholar

[3] S. Andrei, W. N. Chin, A. M. K. Cheng, and M. Lupu: IEEE Transactions on Computers Vol. 55(7) (2006), p.830—842.

Google Scholar

[4] D. Weinland, R. Ronfard, and E. Boyer: Computer Vision and Image Understanding Vol. 115(2) (2011), p.224—241.

DOI: 10.1016/j.cviu.2010.10.002

Google Scholar

[5] L. Lovász, and I. Deák: European Journal of Operational Research Vol. 216(1) (2012), pp.152-161.

Google Scholar

[6] B. Büeler, A. Enge, and K. Fukuda, in: Polytopes—combinatorics and computation, (2000).

Google Scholar

[7] C. Ge, F. Ma, and J Zhang: arXiv preprint arXiv: 1401. 0120. (2013).

Google Scholar

[8] I. Z. Emiris, and V. Fisikopoulos: arXiv preprint arXiv: 1312. 2873. (2013).

Google Scholar

[9] C. B. Barber, D. P. Dobkin, and H. Huhdanpaa: ACM Transactions on Mathematical Software (TOMS) Vol. 22(4) (1996), pp.469-483.

DOI: 10.1145/235815.235821

Google Scholar

[10] B. Korte, and J. Vygen: Combinatorial optimization. Heidelberg: Springer-Verlag, (2002).

Google Scholar