On a cone covering problem

Khaled Elbassioni, Hans Raj Tiwary

Research output: Contribution to conferencePaperpeer-review


Given a set of polyhedral cones C1, · · ·,Ck ⊂ ℝd, 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 entire ℝd or an affine subspace ℝt. As a consequence, we show that the problem of checking if the union of a given set of convex polytopes is convex is coNP-complete, thus answering a question of Bemporad et al. [3].

Original languageBritish English
Number of pages4
StatePublished - 2008
Event20th Annual Canadian Conference on Computational Geometry, CCCG 2008 - Montreal, QC, Canada
Duration: 13 Aug 200815 Aug 2008


Conference20th Annual Canadian Conference on Computational Geometry, CCCG 2008
CityMontreal, QC


Dive into the research topics of 'On a cone covering problem'. Together they form a unique fingerprint.

Cite this