An algorithm for enumerating all vertices of a convex polyhedron
Tóm tắt
A bounded, convex polyhedronP inR
n
can be defined as the intersection of a finite number of halfspaces. Frequently, such polyhedronsP form the feasible regions of optimization problems; sometimes an optimum can only be determined when all vertices ofP are known. This paper describes an algorithm to enumerate these vertices with the help of graphs and a concept by Mañas and Nedoma [2]. Using this algorithm, it will be attempted to estimate the expected number of vertices of the examples employed by Liebling [1].
Tài liệu tham khảo
Liebling, Th. M.: On the Number of Iterations of the Simplex Method. Methods of Operations Research17, 248–264 (1973).
Mañas, M., Nedoma, J.: Finding all Vertices of a Convex Polyhedron. Numerische Mathematik12, 226–229 (1968).
Dantzig, G. B.: Linear Programming and Extensions. Princeton University Press 1973.
Sachs, H.: Einführung in die Theorie der endlichen Graphen, Teil I+II. Leipzig: Teubner Verlagsgesellschaft 1970, 1972.
Grünbaum, B.: Convex Polytopes. New York: J. Wiley 1967.
Rényi, A., Sulanke, R.: Über die konvexe Hülle vonn zufällig gewählten Punkten I, II. Z. Wahrscheinlichkeitstheorie verw. Gebiete2, 75–84 (1963);3, 138–147 (1964).
Rényi, A., Sulanke, R.: Zufällige konvexe Polygone in einem Ringebiet. Z. Wahrscheinlichkeitstheorie verw. Gebiete9, 146–157 (1968).
Carnal, H.: Die konvexe Hülle vonn rotationssymmetrisch verteilten Punkten. Z. Wahrscheinlichkeitstheorie verw. Gebiete15, 168–176 (1970).
Schmidt, W. M.: Some Results in Probabilistic Geometry. Z. Wahrscheinlichkeitstheorie verw. Gebiete9, 158–162 (1968).
Gale, D.: On the Number of Faces of a Convex Polytope. Can. J. Math.16, 12–17 (1964).
Klee, V.: On the Number of Vertices of a Convex Polytope. Can. J. Math.16, 701–720 (1964).