On a cone covering problem

Khaled Elbassioni; Hans Raj Tiwary

doi:10.1016/j.comgeo.2010.07.004

On a cone covering problem

Khaled Elbassioni, Hans Raj Tiwary

Electrical Engineering

TU-Berlin

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

Given a set of polyhedral cones C1,...,CkRd, 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.

Original language	British English
Pages (from-to)	129-134
Number of pages	6
Journal	Computational Geometry: Theory and Applications
Volume	44
Issue number	3
DOIs	https://doi.org/10.1016/j.comgeo.2010.07.004
State	Published - Apr 2011

Keywords

Convexity testing
Polyhedral cones
Union
Vertex enumeration

Access to Document

10.1016/j.comgeo.2010.07.004

Cite this

@article{b2b393ba6d3b4426af28b9ea39843b32,

title = "On a cone covering problem",

abstract = "Given a set of polyhedral cones C1,...,CkRd, 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, Polyhedral cones, Union, Vertex enumeration",

author = "Khaled Elbassioni and Tiwary, {Hans Raj}",

year = "2011",

month = apr,

doi = "10.1016/j.comgeo.2010.07.004",

language = "British English",

volume = "44",

pages = "129--134",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - On a cone covering problem

AU - Elbassioni, Khaled

AU - Tiwary, Hans Raj

PY - 2011/4

Y1 - 2011/4

N2 - Given a set of polyhedral cones C1,...,CkRd, 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.

AB - Given a set of polyhedral cones C1,...,CkRd, 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.

KW - Convexity testing

KW - Polyhedral cones

KW - Union

KW - Vertex enumeration

UR - http://www.scopus.com/inward/record.url?scp=78649319826&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2010.07.004

DO - 10.1016/j.comgeo.2010.07.004

M3 - Article

AN - SCOPUS:78649319826

SN - 0925-7721

VL - 44

SP - 129

EP - 134

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 3

ER -

On a cone covering problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this