## Checking if one polytope is contained in another

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Hi,

I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other.

At the moment I am checking, for each row $a \in A$, whether there exists some $x$ satisfying $ax > 0$ but $Bx \leq 0$. Is there a more efficient approach?

Thanks

-

## 1 Answer

I would like to draw your attention to the 2002 survey by Volker Kaibel and Marc Pfetsch, "Some Algorithmic Problems in Polytope Theory," arXiv:math/0202204v1, which contains this on p.6:

As you probably know, an $\cal{H}$-description is by halfspaces, whereas a $\cal{V}$-description is by vertices. Reference [20] is: R. M. Freund and J. B. Orlin, "On the complexity of four polyhedral set containment problems," Math. Program., 33 (1985), pp. 139–145. Reference [17] is B. C. Eaves and R. M. Freund, "Optimal scaling of balls and polyhedra," Math. Program., 23 (1982), pp. 138–147.

-

Thanks! That survey is just what I've been looking for. – bandini Apr 10 2012 at 23:12
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 8, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9085538387298584, "perplexity_flag": "middle"}