On a cone covering problem

Given a set of polyhedral cones C1, · · · , Ck ⊂ Rd, and a convex set D, does the union of these cones cover the set D? In this paper we consider the computa-tional complexity of this problem for various cases such as whether the cones are defined by extreme rays or facets, and whether D is the entire Rd or a given linear subspace Rt. As a consequence, we show that it is coNP-complete to decide if the union of a given set of convex polytopes is convex, thus answering a question of Bemporad, Fukuda and Torrisi. 1