On a cone covering problem |
| |
Authors: | Khaled Elbassioni |
| |
Institution: | a Max-Planck-Institut für Informatik, Saarbrücken, D-66123 Germany b Technische Universität, MA 6-2, Institut für Mathematik, 10623 Berlin, Germany |
| |
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. |
| |
Keywords: | Convexity testing Union Polyhedral cones Vertex enumeration |
本文献已被 ScienceDirect 等数据库收录! |
|