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.

  1. 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.
  2. Золотых Н.Ю. Новая модификация метода двойного описания для построения остова многогранного конуса // Журнал вычислительной математики и математической физики. - 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
  3. 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.


News

14 May 2013
Skeleton 02.01.05 is released

10 June 2012
Skeleton 02.01.04 is released

19 October 2010
Skeleton 02.01.03 is released

15 July 2010
Skeleton 02.01.02 is released

11 July 2010
Skeleton 02.01.01 is released


Files


Related Software and Links

  • Komei Fukuda's CDD: another implementation of DDM
  • David Avis' lrs the reverse search algorithm
  • pd: Primal-Dual Methods for Vertex and Facet Enumeration by David Bremner, Komei Fukuda and Ambros Marzetta
  • Qhull: Quickhull algorithm for computing the convex hull, Delaunay triangulation, etc., floating point arithmetic, by C.B. Barber, D.P. Dobkin, H.T. Huhdanpaa
  • Polymake: System dealing with convex polyhedra, simplicial complexes, tight spans, polyhedral surfaces, and other objects by Ewgenij Gawrilow and Michael Joswig
  • David Bremner's Discussion of Vertex/Facet Enumeration Software


Matlab Wrapper


my home page