VERTEX ENUMERATION OF POLYHEDRA

ABSTRACT The vertex enumeration problem of a polyhedron P in ℜ n , given by m inequalities, is widely discussed in the literature. In this work it is introduced a new algorithm to solve it. The algorithm is based on lexicographic pivoting and the worst-case time complexity is O m m + n 2 × m i n m , n which is O m n V P for the case of non-degenerate polyhedra, where V P is the number of vertices of P. The proposed algorithm was coded in Matlab and numerical experiments performed for several randomly generated problems show its efficiency.