Abstract.
Our main result is that every n-dimensional polytope can be described by at most 2n−1 polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an n-dimensional pointed polyhedral cone we prove the bound 2n−2 and for arbitrary polyhedra we get a constructible representation by 2n polynomial inequalities.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Applegate, D., Bixby, R., Chvátal, V., Cook, W.: On the solution of traveling salesman problems, Doc. Math., J. DMV, Extra Vol. ICM Berlin 1998 III (1998), 645–656.
Andradas, C., Bröcker, L., Ruiz, J.M.: Constructible sets in real geometry, Springer, Berlin, (1996)
Bochnak, J., Coste, M., Roy, M.-F.: Real algebraic geometry, Springer, New York, (1998)
Bernig, A.: Constructions for the theorem of Bröcker and Scheiderer, Master’s thesis, Universität Dortmund, (1998)
Bosse, H.: Describing polyhedra by polynomial inequalities, Master’s thesis, Technische Universität Berlin, (2003)
Bröcker, L.: On basic semialgebraic sets, Expo. Math. 9, 289–334 (1991)
Grötschel, M., Henk, M.: The representation of polyhedra by polynomial inequalities, Discrete Comput. Geom. 29 (2003), no. 4, 485–504.
Grötschel, M., Lovász, L., Schrijver, A.: Geometric algorithms and combinatorial optimization, 2nd, corr. ed., 3rd printing ed., Algorithms and Combinatorics, vol. 2, Springer, Berlin Heidelberg, (1993)
Mahé, L.: Une démonstration élémentaire du théoréme de Bröcker-Scheiderer, C.R. Acad. Sc. Paris 309 (1989), no. I, 613–616.
McMullen P., Shephard, G.C.: Convex polytopes and the upper bound conjecture, Cambridge University Press, Cambridge, (1971)
Scheiderer, C.: Stability index of real varieties, Inventiones Math. 97 (1989), no. 3, 467–483.
vom Hofe, G.: Beschreibung von ebenen konvexen n-Ecken durch höchstens drei algebraische Ungleichungen, Ph.D. thesis, Universität Dortmund, (1992)
Ziegler, G.M.: Lectures on polytopes, Springer, Berlin, 1995.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the DFG Research Center “Mathematics for key technologies” (FZT 86) in Berlin.
Rights and permissions
About this article
Cite this article
Bosse, H., Grötschel, M. & Henk, M. Polynomial inequalities representing polyhedra. Math. Program. 103, 35–44 (2005). https://doi.org/10.1007/s10107-004-0563-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-004-0563-2