On K[Delta]

Abstract

Let K be an unbounded convex polyhedral subset of Rn represented by a system of linear constraints, and let K[Delta] be the convex hull of the set of extreme points of K. We show that the combinatorial-facial structure of K does not uniquely determine the combinatorial-facial structure of K[Delta]. We prove that the problem of checking whether two given extreme points of K are nonadjacent on K[Delta], is NP-complete in the strong sense. We show that the problem of deriving a linear constraint representation of K[Delta], leads to the question of checking whether the dimension of K[Delta] is the same as that of K, and we prove that resolving this question is hard because it needs the solution of some NP-complete problems. Finally we provide a formula for the dimension of K[Delta], under a nondegeneracy assumption.