On KΔ

AbstractLet K be an unbounded convex polyhedral subset of Rn represented by a system of linear constraints, and let KΔ 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Δ. We prove that the problem of checking whether two given extreme points of K are nonadjacent on KΔ, is NP-complete in the strong sense. We show that the problem of deriving a linear constraint representation of KΔ, leads to the question of checking whether the dimension of KΔ 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Δ, under a nondegeneracy assumption