Skeleton: Implementation of Double Description Method
Skeleton is a new fast implementation of
Double Description Method (DDM) [1] for generating all extreme rays of a polyhedral cone.
Float, integer and arbitrary precision integer arithmetics is supported.
The implementation uses Arageli
library for exact computation. The latest version: Skeleton 02.01.01 - July 11, 2010.
[1]
T.S. Motzkin, H. Raiffa, G.L. Thompson, and R.M. Thrall.
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.
Skeleton online
You can try skeleton online. Thanks to Sergey V. Lobanov.
MATLAB wrapper for Skeleton
My MATLAB wrapper. Dec. 22 2009. New! Only float double precision arithmetic.
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
Nikolai Yu. Zolotykh
my home page