Skeleton: Implementation of Double Description Method

Convex Hull Problem and Solving Systems of Linear Inequalities

Home | News | Files | Related Software and Links | Matlab Wrapper

| Tell your friends about this site: | RSS feed:

Skeleton is a new fast implementation of Double Description Method (DDM) [1] for generating all extreme rays of a polyhedral cone and, consequently, for solving the vertex and facet enumeration problems for convex polyhedra. Using Skeleton you can solve convex hull problem in d-dimensinal space. Also, you can find all solutions to a system of linear inequalities.
New enhancements [2] make Skeleton very competitive in comparison with other implementations of DDM and other methods for solving these problems.
Float, integer and arbitrary precision integer arithmetics is supported. The implementation uses Arageli library for exact computation.
Please cite [2] in your publication if you use Skeleton.
A descendant of Skeleton is S. Bastrakov's qskeleton that uses a lot of new enchancements [3]. We note that not all features of skeleton is supported in qskeleton.

Motzkin T.S., Raiffa H., Thompson G.L., Thrall R.M. The double description method. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games - Volume II, number 28 in Annals of Mathematics Studies, pages 51-73. Princeton University Press, Princeton, New Jersey, 1953.
Золотых Н.Ю. Новая модификация метода двойного описания для построения остова многогранного конуса // Журнал вычислительной математики и математической физики. - 2012. - Т. 52, N 1. - С. 153-163. pdf English transl.: Zolotykh N.Yu. New modification of the double description method for constructing the skeleton of a polyhedral cone // Computational mathematics and mathematical physics. - 2012. - V. 52, N.1. - P.146-156. pdf
Bastrakov S.I., Zolotykh N.Yu. Application of the Quickhull algorithm's principles to the double description method // Numerical Methods and Programming/ 2011. V. 12. P. 232-237 (in Russian)

On the figure: truncated icosahedron (soccer ball). This is a Leonardo's drawing called by him Ycocedron Abscisus Vacuus in Luca Pacioli's 1509 book De Devina Proportione. See, for example, Leonardo Page which is a part of George W. Hart's Virtual Polyhedra Pages.