An algorithm for enumerating all vertices of a convex polyhedron
Tóm tắt
A bounded, convex polyhedronP inR
n
can be defined as the intersection of a finite number of halfspaces. Frequently, such polyhedronsP form the feasible regions of optimization problems; sometimes an optimum can only be determined when all vertices ofP are known. This paper describes an algorithm to enumerate these vertices with the help of graphs and a concept by Mañas and Nedoma [2]. Using this algorithm, it will be attempted to estimate the expected number of vertices of the examples employed by Liebling [1].