Skeleton: Implementation of Double Description Method

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

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

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.