| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 414266 | Computational Geometry | 2011 | 6 Pages |
Abstract
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 computational 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
