The use of edge-directions and linear programming to enumerate vertices

Given a list of vectors that contains directions of the edges of a given polytope ℘ and the availability of an algorithm that solves linear programs over ℘, we describe a method for enumerating the vertices of ℘; in particular, the method is adaptable to polytopes which are presented as (linear) projections of polytopes having linear inequality representation. Polynomial complexity bounds under both the real and the binary computation models are derived when the dimension of the polytope is fixed and the given LP algorithm is polynomial. Dedicated to Professor Frank K. Hwang on the occasion of his sixty fifth birthday. Supported in part by a grant from ISF—the Israel Science Foundation, by a VPR grant at the Technion and by the Fund for the Promotion of Research at the Technion.