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:
KP Problems http://cs.smith.edu/%7Eorourke/MathOverflow/KPProblems.jpg
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.
Joseph O'Rourke
- 150.8k
- 36
- 358
- 958