## Primal-Dual Methods for Vertex and Facet Enumeration

### Abstract

Every convex polytope can be represented as the intersection of a
finite set of halfspaces and as the convex hull of its vertices.
Transforming from the halfspace (respectively vertex) to the vertex
(respectively halfspace) representation is called
**vertex enumeration** (respectively **facet enumeration**). An
open question is whether there is an algorithm for these two
problems (equivalent by geometric duality) that is polynomial in
the input size and the output size. In this paper, we extend the
known polynomially solvable classes of polytopes by looking at the
dual problems. The **dual** problem of a vertex (facet,
respectively) enumeration problem is the facet (vertex) enumeration
problem for the same polytope where the input and output are simply
interchanged. For a particular class of polytopes and a fixed
algorithm, one transformation may be much easier than its dual. In
this paper, we propose a new class of algorithms that take
advantage of this phenomenon. Loosely speaking, **primal-dual**
algorithms use a solution to the easy direction as an oracle to
help solve the seemingly hard direction.

### The Implementation Is Available Here

We have implemented a primal-dual algorithm using rational arithmetic in C. It is most efficient for facet enumeration of simple polytopes and vertex enumeration of simplicial polytopes. It accepts input files in .ine-format like cdd, prs and lrs. gzipped tarfile of source code Don't forget to read the Manual.

### References David Bremner,

Komei Fukuda and Ambros Marzetta, Primal-Dual Methods for Vertex and Facet Enumeration, 13th ACM Symposium on Computational Geometry SCG 1997, 49-56. David Bremner, Komei Fukuda and Ambros Marzetta, Primal-Dual Methods for Vertex and Facet Enumeration, Discrete and Computational Geometry 20:333-357 (1998).

This page originally by Ambros Marzetta