Geodesic
Elimination of inequalities from a facet description of a polyhedron
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 3, pp. 37-45

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the following problem: given vertex and facet representations of a convex polyhedron, compute a vertex representation of the polyhedron defined by a subsystem of inequalities of the original polyhedron. We present a new algorithm, prove its correctness, and give upper bounds for the complexity. Unlike other approaches, the proposed algorithm is polynomial for the case of removing one inequality. Computational experiments show that the algorithm outperforms the incremental method in a number of cases.
Keywords: convex polyhedra, constraint removal, double description method. 
@article{TIMM_2015_21_3_a4,
     author = {S. Bastrakov and N. Yu. Zolotykh},
     title = {Elimination of inequalities from a facet description of a polyhedron},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {37--45},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a4/}
}
TY  - JOUR
AU  - S. Bastrakov
AU  - N. Yu. Zolotykh
TI  - Elimination of inequalities from a facet description of a polyhedron
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2015
SP  - 37
EP  - 45
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a4/
LA  - ru
ID  - TIMM_2015_21_3_a4
ER  - 
%0 Journal Article
%A S. Bastrakov
%A N. Yu. Zolotykh
%T Elimination of inequalities from a facet description of a polyhedron
%J Trudy Instituta matematiki i mehaniki
%D 2015
%P 37-45
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a4/
%G ru
%F TIMM_2015_21_3_a4
S. Bastrakov; N. Yu. Zolotykh. Elimination of inequalities from a facet description of a polyhedron. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 3, pp. 37-45. http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a4/