Generated on Tue Jan 30 13:26:25 2001

# Sections

Feedback

I Algorithms

next section        top

1. W. Altherr. An algorithm for enumerating the vertices of a convex polyhedron. Computing, 15:181--193, 1975.
vertex-enumeration
2. Nancy M. Amato, Micheal T. Goodrich, and Edgar A. Ramos. Parallel algorithms for higher-dimensional convex hulls. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 683--694, 1994.
A parallel randomized algorithm that constructs the convex hull in $O(\logn)$ time and $O(n \log n + n^{\lfloor d/2 \rfloor})$ work, where $d$ is assumed to be constant. Uses a modified notion of cutting (see [119]) to decompose the space (rather than the input halfspaces) in order to do divide and conquer.
parallel, facet-enumeration, fixed-dimension
3. D. Avis, D. Bremner, and R. Seidel . How good are convex hull algorithms? Computational Geometry: Theory and Applications, 7:265--302, 1997. http://www.cs.unb.ca/~bremner/research/papers/abs-hgach-97.ps.gz
vertex-enumeration, facet-enumeration, dwarfed, lower bounds
4. David Avis and David Bremner . How good are convex hull algorithms? In Proceedings of the 11th ACM Symposium on Computational Geometry, pages 20--28, 1995.
Provides classes of hard polytopes for pivoting algorithms using perturbation, algorithms using triangulation, and some insertion algorithms. Gives experimental results for these hard classes on current implementations.
5. David Avis and David Bremner . Large convex hull problems. Zeitschrift f{\"u}r Angewandte Mathematik und Mechanik, 87(3):179--182, July 1995. Special Issue: {Proceedings of the Third International Congress on Industrial and Applied Mathematics}.
vertex-enumeration, facet-enumeration, lower bounds, estimation
6. David Avis and Luc Devroye . Estimating the number of vertices of a polyhedron. In David Avis and Prosenjit Bose, editors, Snapshots in Computational and Discrete Geometry, volume 3, pages 179--190. School of Computer Science, McGill University, 1994.
Uses reverse search [7] to estimate the number of feasible bases and vertices of a polytope.
vertex-enumeration, pivoting, random, estimation
7. David Avis and Komei Fukuda . A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete and Computational Geometry, 8:295--313, 1992.
Describes the notion of {\em reverse search\/}. By considering the paths taken by the simplex method from every vertex to some optimal vertex, an implicit tree is induced on the vertices (or bases) of the polytope. Depth first search on this tree allows generation of all feasible bases with memory usage proportional to the input.
vertex-enumeration, pivoting
8. K.H. Borgwardt. Average complexity for determining the convex hull of randomly given points. Discrete and Computational Geometry, 17:79--109, 1997.
Gives a probabilistic analysis of a gift wrapping algorithm (see e.g. [55, 20]) on random input. The claim is that for random input, redundant points need not be removed by preprocessing.
facet-enumeration, random, extreme-point computation
9. O. Bournez, O. Maler, and A. Pnueli . Orthogonal polyhedra: Representation and computation. In F. Vaandrage and J. van Schuppen, editors, Hybrid Systems: Computation and Control, LNCS 1569. ftp://ftp.imag.fr/imag/SPECTRE/ODED/griddy.ps.gz Springer, 1999.
\emph{Author Abstract.}\quad In this paper we investigate orthogonal polyhedra, i.e. polyhedra which are finite unions of full-dimensional hyper-rectangles. We define representation schemes for these polyhedra based on their vertices, and show that these compact representation schemes are canonical for all (convex and non-convex) polyhedra in any dimension. We then develop efficient algorithms for membership, face-detection and Boolean operations for these representations.
non-convex, parallelapiped
10. David Bremner. Incremental convex hull algorithms are not output sensitive. In Proceedings of the International Symposium on Algorithms and Computation '96, volume 1178 of Lecture Notes on Computer Science, pages 26--35. Springer-Verlag, December 1996. http://www.cs.unb.ca/~bremner/research/papers/b-ichan-98.ps.gz
Gives examples of families of polytopes for which any order of incremental construction builds intermediate polytopes with size superpolynomial in the input and output size.
incremental, combinatorial structure, facet-enumeration, vertex-enumeration, lower bounds
11. David Bremner. On the complexity of vertex and facet enumeration for convex polytopes. PhD thesis, School of Computer Science, McGill University, 1997. http://www.cs.unb.ca/~bremner/research/papers/phd
combinatorial structure, vertex-enumeration, facet-enumeration, algorithms, lower bound
12. David Bremner. Incremental convex hull algorithms are not output sensitive. Discrete and Computational Geometry, 21(1):57--68, January 1999. http://www.cs.unb.ca/~bremner/research/papers/b-ichan-98.ps.gz
incremental, facet-enumeration, vertex-enumeration, lower bounds
13. David Bremner, Komei Fukuda, and Ambros Marzetta. Primal dual methods for vertex and facet enumeration. Discrete and Computational Geometry, 20(3):333--357, October 1998. Invited paper. http://www.cs.unb.ca/~bremner/research/papers/bfm-pdmvf-98.ps.gz
facet-enumeration, implementation, pivoting, incremental
14. Adrian Br{\"u}ngger, Ambros Marzetta, Komei Fukuda, and Jurg Nievergelt. The parallel search bench ZRAM and its applications. Annals of Operations Research, to appear.
Discusses a parellel implementation of \textttlrs [58]
vertex-enumeration, pivoting, parallel
15. E. Burger. {\"U}ber homogene lineare Ungleichungssysteme. Zeitschrift f{\"u}r Angewandte Mathematik und Mechanik, 36:135--139, 1956.
Contains a description of the double description method.
vertex-enumeration, double-description, incremental
16. Michael R. Bussieck and Marco E. L{\"u}bbecke. The vertex set of a 0/1-polytope is strongly P-enumerable. http://www.math.tu-bs.de/mo/research/zerone.html 1998.
zero-one, vertex-enumeration
17. Burdet C.-A.. Generating all faces of a polyhedron. SIAM J. Appl. Math., 26:479--489, 1974.
face-enumeration
18. Timothy M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. In Proceedings of the 11th ACM Symposium on Computational Geometry, pages 10--19, 1995.
Output sensitive algorithms for points in general position and dimension fixed. Uses ray shooting data-structures.
facet-enumeration, fixed-dimension, general-position, output-sensitive
19. Timothy M. Chan, Jack Snoeyink, and Chee-Keng Yap. Primal dividing and dual pruning: Output-sensitive construction of 4-d polytopes and 3-d voronoi diagrams. In Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, pages 282--291, 1995.
20. D.R. Chand and S.S. Kapur . An algorithm for convex polytopes. Journal of the ACM, 17:78--86, 1970.
A (dual) pivoting algorithm, also known as gift wrapping''. Analyzed in [55].
21. A. Charnes. The simplex method: optimal set and degeneracy. In An introduction to Linear Programming, Lecture VI, pages 62--70. Wiley, New York, 1953.
Suggests a method for enumerating the optimal solutions to a linear program based on the simplex pivots and depth first search. Includes a perturbation procedure.
perturbation, degeneracy, vertex-enumeration, pivoting
22. Bernard Chazelle. An optimal convex hull algorithm in any fixed dimension. Discrete and Computational Geometry, 10:377--409, 1993.
An insertion based algorithm that achieves a time bound of $O(n^{\lfloor d/2 \rfloor})$ in fixed dimension $d$.
facet-enumeration, incremental, fixed-dimension
23. Pey-Chun Chen, Pierre Hansen, and Brigitte Jaumard. On-line and off-line vertex enumeration by adjacency lists. Operations Research Letters, 10:403--409, 1991.
The on-line vertex enumeration problem is to intersect a polytope with a halfspace. Includes details on the standard combinatorial adjacency checking for vertices, used for example in {\tt cdd} [63].
vertex-enumeration, incremental
24. N.V. Chernikova. Algorithm for finding a general formula for the non-negative solutions of a system of inequalities. U.S.S.R. Comput. Math. Phys., 5:228--233, 1965.
The double description method [45], with the implementation simplifying assumption that the variables are non-negative.
vertex-enumeration, double-description, incremental
25. Kenneth L. Clarkson . More output-sensitive geometric algorithms. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pages 695--702, 1994. http://www.cs.att.com/netlib/att/cs/doc/94/2-13.ps.Z
Gives a method for finding extreme points in $d$ dimensions where the row size of the linear programs solved is bounded above by the output size. Uses this method in a convex hull'' algorithm that computes the face lattice.
extreme-point computation, face-enumeration, output-sensitive
26. Kenneth L. Clarkson and Peter W. Shor . Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incremental. In Proceedings of the 4th ACM Symposium on Computational Geometry, pages 12--17, 1988.
A randomized insertion algorithm. Uses triangulation.
random sampling, k-sets, convex hull, diameter
27. Martin E. Dyer. The complexity of vertex enumeration methods. Mathematics of Operations Research, 8(3):381--402, 1983.
Uses a result of Klee [171] to show that insertion algorithms that insert the constraints in the order given are exponential in the worst case. Also gives a pivoting algorithm based on breadth first search
vertex-enumeration, lower-bounds, incremental, pivoting
28. Martin E. Dyer and L.G. Proll . An algorithm for determining all extreme points of a convex polytope. Mathematical Programming, 12:81--96, 1977.
A pivoting algorithm based on breadth first search of the pivot graph. Contains about 10 references to applications of vertex enumeration.
vertex-enumeration, pivoting
29. Herbert Edelsbrunner . Algorithms in Combinatorial Geometry, chapter 8.4, pages 147--158. Volume 10 of {\em EATCS Monographs on Th. Comp. Sci.\/} [156], 1987.
Description of the beneath and beyond method in $d$-dimensions. Written by Raimund Seidel. Achieves a time bound of $O(n^{\lfloor d/2 \rfloor})$ in fixed even dimension $d$.
facet-enumeration, vertex-enumeration, incremental
30. Jack Edmonds. Decomposition using Minkowski. Abstracts of the 14th International Symposium on Mathematical Programming, Amsterdam, 1991.
Gives a recursive procedure that given $P=\set{x \mid Ax \leq b}$, and a point $z$ interior to $P$, computes $d+1$ or fewer extreme points of $P$ that contain $z$ in their convex hull. This procedure can be implemented to run in time $O(md^3)$, where $m$ is the row size of $A$.
pivoting, linear inequality, Minkowski-Weyl Theorem
31. Jean Baptiste Joseph Fourier . Histoire de l'Academie Royale des Sciences de l'Institute de France, volume 7, pages xlvii--lv. l'Imprimerie de Du Pont, pere et fils, Paris, 1824. Reprinted in [32]. English translation in [38].
Sketches the (geometric) simplex method and describes the method for finding all extremal solutions of a system of linear inequalities now known as Fourier-Motzkin Elimination
pivoting, incremental, Fourier-Motzkin elimination
32. Jean Baptiste Joseph Fourier . \OE{}uvres de Fourier. Gauthier-Villars et Fils, Paris, 1890.
33. Komei Fukuda. Lecture notes: Combinatorics of mathematical programming and polyhedral geometry. EPFL, Lausaunne Switzerland, 1993.
34. Komei Fukuda, Thomas M. Liebling, and Fran\c{}ois Margot. Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron. Computational Geometry: Theory and Applications, 8:1--12, 1997.
Contains an algorithm to compute the $\fb$ faces of a polytope with $m$ facets and $n$ vertices in time $O(\fb m\,L(m,n))$ where $L(m,n)$ is the amount of time necessary to solve an $m$ by $n$ linear program.
vertex-enumeration, face-enumeration, NP-Complete
35. Komei Fukuda and Alain Prodon . Double description method revisited. In Combinatorics and computer science (Brest, 1995), volume 1120 of Lecture Notes in Comput. Sci., pages 91--111. Springer-Verlag, Berlin, 1996.
incremental, vertex-enumeration, double-description, implementation
36. Komei Fukuda and Vera Rosta . Combinatorial face enumeration in convex polytopes. Comput. Geom. Theory Appl., 4:191--198, 1994.
Gives a combinatorial algorithm to enumerate the $\fb$ faces of a $d$-polytope with $m$ facets and $n$ vertices in time $O(\fb^2\min(m,n))$. Requires vertex/facet incidence information as input.
face-enumeration
37. Peter Gritzmann and Victor Klee . On the complexity of some basic problems in computational convexity: II. Volume and mixed volumes. In Bistztriczky et al. [144], pages 373--466.
Gives a vertex enumeration algorithm polynomial for simplicial polytopes based on intersecting the constraints with each bounding hyperplane, using linear programming to remove redundant constraints, and enumerating the vertices of the simplicial facet by brute force.
volume, polytope, computation
38. D.A. Kohler. Translation of a report by Fourier on his work on linear inequalities. Opsearch, 10:38--42, 1973. Translation of [31].
39. T.H. Matheiss and David S. Rubin . A survey and comparison of methods for finding all vertices of convex polyhedral sets. Mathematics of Operations Research, 5:165--185, 1980.
A survey of early algorithms for vertex enumeration, with experimental results.
40. Miroslav Ma\vnas and Josef Nedoma . Finding all vertices of a convex polyhedron. Numerische Mathematik, 12:226--229, 1968.
Pivoting algorithm. Does breadth first search on the basis graph.
41. Kurt Mehlhorn. Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry, volume 3 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Heidelberg, West Germany, 1984.
data structures, algorithms, computational geometry, book
42. Theodore S. Motzkin . Beitr{\"a}ge zur Theorie der linearen Ungleichungen. Doktorarbeit, Universit{\"a}t Basel, 1933. Published in Jerusalem in 1936, English translation in [43, 44].
Sketches the double description method (i.e. successive intersection of halfspaces) in a proof of a generalization of a finite basis theorem of Minkowski (\parasign 30). Gives a more complete description of the elimination procedure introduced by Fourier [31] (\parasign 87).
Fourier-Motzkin elimination, double-description
43. Theodore S. Motzkin . Contributions to the theory of linear inequalites. Number 22 in RAND Corporaton Translations. Rand Corporation, 1952. English translation of [42]. Reprinted in [44].
Fourier-Motzkin elimination, double-description
44. Theodore S. Motzkin . Contributions to the theory of linear inequalites. In David Cantor, Basil Gordon, and Bruce Rothschild, editors, Theodore S. Motzkin: Selected Papers. Birkhauser, 1983.
45. Theodore S. Motzkin, H. Raiffa, G.L. Thompson, and R. M. Thrall. The double description method. In H.W. Kuhn and A.W. Tucker , editors, Contributions to the Theory of Games II, volume 8 of Annals of Math. Studies, pages 51--73. Princeton University Press, 1953.
The first widely available description of an insertion or incremental algorithm for vertex and extreme ray enumeration. Also describes application to two player games
46. K.G. Murty. Solving the fixed charge problem by ranking the extreme points. Operations Research, 16:268--279, 1968.
According to [39]: uses the fact that if vertices are ordered in nondecreasing order by linear objective $cx$, then $v_{k+1}$ must be adjacent to one of $v_1\ldots v_k$. Stores with each vertex the pivots (edges in basis graph), along with the resulting objective values. At each step the lowest valued edge is expanded
47. J. Scott Provan. Efficient enumeration of the vertices of polyhedra associated with network {LP's}. Mathematical Programming, 63:47--64, 1994.
Gives a polynomial algorithm for vertex enumeration of network polyhedra and dual network polyhedra
48. G{\"u}nter Rote. Degenerate convex hulls in high dimensions without extra storage. In Proceedings of the 8th ACM Symposium on Computational Geometry, pages 26--32, 1992.
Reverse search on facets rather than bases. Requires traversal of the face lattice of each facet to determine ridges.
49. Raimund Seidel. A convex hull algorithm optimal for point sets in even dimensions. Master's thesis, University of British Columbia, Dept. of Computer Science, 1981. Report 81-14.
Achieves a time bound of $O(n^{\lfloor d/2 \rfloor})$ in fixed even dimension $d$.
facet-enumeration, incremental
50. Raimund Seidel. Constructing higher-dimensional convex hulls at logarithmic cost per face. In Proceedings of the 18th ACM Symposium on the Theory of Computing, pages 404--413, 1986.
Uses shellings to get output sensitive time for fixed dimension and points in general position.
convex hull, incidence graph, polyhedra, linear programming, output-sensitive
51. Raimund Seidel. Output-size sensitive algorithms for constructive problems in computational geometry. Ph.D. thesis, Dept. Comput. Sci., Cornell Univ., Ithaca, NY, 1986. Technical Report TR 86-784.
Uses shellings to get output sensitive time for fixed dimension and points in general position
doctoral thesis, incidence graph, divide-and-conquer, plane-sweep, domination, intersection, facet-enumeration, vertex-enumeration, output-sensitive
52. G.J. Silverman. Computational considerations in extreme point computation. Report 320-2649, IBM L.A. Research Center, 1971.
Tries to find a G-path'' $\Pi$ s.t. every vertex is either on $\Pi$ or adjacent to it.
vertex-enumeration, algorithms
53. William Mott Stewart . Efficient Incremental Construction of Convex Hulls from Spherical Distributions in Higher Dimensions. PhD thesis, University of New Brunswick, 1992.
The incremental construction of convex hulls is investigated. Given a set of n points S in $\Re^d$ in general position, a data structure is given and an algorithm implemented to add a point to an existing convex hull in $\Theta$($d^3$) expected time in the number of new facets created. \emph{Start of author abstract}. See also [8] for more on spherical distributions.
facet-enumeration, extreme-point computation, random
54. Ruth Wycliffe Stokes . A geometric theory of solution of linear inequalities. Transactions of the American Mathematical Society, 33:782--805, 1931.
Gives a geometric dual to Minkowski's algorithm [163].
55. Garret Swart. Finding the convex hull facet by facet. Journal of Algorithms, pages 17--48, 1985.
Gives an analysis of Chand and Kapur's dual pivoting algorithm [20]. Contains a modification of [20] that computes the face lattice in time polynomial in the input and output size.
56. T. Yamada, J. Yoruzuya, and S. Kataoka . Enumerating extreme points of a highly degenerate polytope. Computers and Operations Research, 21(4):397--410, 1994.
A recursive pivoting algorithm for vertex enumeration that amounts to enumerating the (dual) abbreviated face lattice (see [55]). The paper also details an optimization for the case when a variable occurs in exactly one constraint.
degeneracy, vertex-enumeration, pivoting

II Implementations

previous section        next section        top

57. D. Alevras, G. Cramer, and M. Padberg . DODEAL, 1994. ftp://elib.zib-berlin.de/pub/mathprog/polyth/dda
Implementation of the double description method, based on [15].
vertex-enumeration, double-description, implementation
58. David Avis. A C implementation of the reverse search vertex enumeration algorithm. Technical Report RIMS Kokyuroku 872, Kyoto University, May 1994. (Revised version of: Technical Report SOCS-92.12, McGill University, School of Computer Science). http://cgm.cs.mcgill.ca/~avis/C/lrs.html
vertex-enumeration, pivoting, implementation
59. C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa. The Quickhull algorithm for convex hull. Technical Report GCG53, Geometry Center, Univ. of Minnesota, July http://www.geom.umn.edu/software/download/qhull.html 1993.
A variant of the beneath and beyond method that inserts points based how far outside the current polytope they are.
facet-enumeration, Voronoi diagram, implementation
60. Thomas Christof and Andreas Loebel . porta. Version 1.3.1, March 1997. http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/PORTA/readme.html
Fourier-Motzkin elimination, with exact arithmetic.
incremental, Fourier-Motzkin elimination, facet-enumeration, vertex-enumeration, implementation
61. Kenneth L. Clarkson . hull 1.0. AT\&T Bell Labs, 1995. http://www.cs.att.com/netlib/voronoi/hull.html
Incremental method working in exact arithmetic when possible''.
incremental, facet-enumeration
62. Ionnis Z. Emiris, John F. Canny, and Raimund Seidel. Efficient perturbations for handling geometric degeneracies. manuscript. ftp://robotics.eecs.Berkeley.edu/pub/ConvexHull
Describes an implementation of the beneath and beyond (incremental) method using perturbation. The implementation is available from the same place.
facet-enumeration, incremental, pivoting
63. Komei Fukuda. {cdd+} Reference manual, version 0.74. ETHZ, Zurich, Switzerland. ftp://ifor13.ethz.ch/pub/fukuda/cdd
C++ implementation of the double description method [45] using exact rational or floating point arithmetic. ANSI C version (floating point only) available at the same location.
vertex-enumeration, facet-enumeration, incremental, double-description, implementation
64. Robert Lum. Finding all vertices of a polyhedron. Master's project, McGill School of Computer Science., August 1980.
Implementation of algorithm from [71]
vertex-enumeration, implementation
65. Ambros Marzetta. {ZRAM:} A library of parallel search algorithms. PhD thesis, ETH Zurich, 1998.
66. Michael M{\"u}ller and Joachim Ziegler . An implementation of a convex hull algorithm. manuscript, January 1995. ftp://ftp.mpi-sb.mpg.de/pub/LEDA/articles/chull.ps.Z
An implemention of an incremental algorithm, using LEDA [67]. Uses triangulation.
67. Stefan N{\"a}her and Christian Urhig . The LEDA User Manual Version R 3.2. http://www.mpi-sb.mpg.de/LEDA/leda.html
C++ library for geometric operations.
68. B. von Hohenbalken . Least distance methods for the scheme of polytopes. Mathematical Programming, 15:1--11, 1978.
Computes the entire face lattice. Provides APL code.
face-enumeration, vertex-enumeration, facet-enumeration, implementation
69. Doran K. Wilde. A library for doing polyhederal applications. Technical Report 785, IRISA, Campus Universitaire de Beaulieu -- ftp://ftp.irisa.fr/local/API 35042 Rennes CEDEX France, 1993.
Describes an implementation of the double description method [45] and its applications to parallelizing compilers and VLSI synthesis.
implementation, double-description, facet-enumeration, vertex-enumeration

III Linear Programming

previous section        next section        top
See also: 21, 33, 103, 124, 129, 150, 154, 165, 166, 171, 174

70. David Avis and Va\vsek Chv{\'a}tal . Notes on Bland's pivoting rule. Math. Programming Study, 8:24--34, 1978.
pivoting, lower bounds
71. Va\vsek Chv{\'a}tal . Linear Programming. W. H. Freeman, New York, NY, 1983.
Good reference and text on the simplex method. Includes duality, complementary slackness, the revised simplex method. Develops everything from elementary principles. Contains a pivoting based algorithm that does breadth first search of the basis graph (Chapter 18).
linear programming, pivoting, vertex-enumeration, book
72. George B. Dantzig, Alex Orden, and Philip Wolfe. The generalized simplex method for minimizing a linear form under liner inequality restraints. Pacific Journal of Mathematics, 5:183--195, 1955.
The canonical description of the simplex method using lexicographic pivoting.
pivoting, perturbation
73. George.B. Dantzig . Maximizing a linear function of variables subject to linear inequalities. In Tj. C. Koopmans , editor, Activity Analysis of Production and Allocation, pages 339--347. Wiley, New York, 1951.
74. Lloyd L. Dines. Systems of linear inequalities. Annals of Mathematics (2), 20:191--199, 1918--1919.
An elimination based method for solving systems of inequalities.
75. Mike Hohmeyer. lp. http://graphics.lcs.mit.edu/~seth/geomlib/lp.tar
Mike Hohmeyer's C implementation of Raimund Seidel's O(d! n) time linear programming algorithm; an extremely useful piece of code in low dimension. [It is in ar format; on a unix system simply invoke 'ar x lp.ar' to unpack the sources.] {\em Notes by Seth Teller}
76. James P. Ignizio and Tom M. Cavalier . Linear Programming. Prentice Hall International Series in Industrial and Systems Engineering. Prentice Hall, 1994.
77. L.V. Kantorovich. My journey in science. Russian Math. Surveys, 42:233--270, 1987.
Discusses early work on the simplex type algorithms.
pivoting
78. Victor Klee and G.J. Minty . How good is the simplex method? In O. Shisha , editor, Inequalities-III, pages 159--175. Academic Press, 1972.
Gave a class of skewed $d$-cubes for which the simplex method using the largest coefficent method visits all vertices
diameter
79. Alexander Schrijver . Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics. Wily-Interscience, New York, 1986.
80. Komei Fukuda. ETH lectures 1995. Lecture Notes.
81. C.H. Papadimitriou and D. Wolfe . The complexity of facets resolved. In Proceedings of the 26th {Ann.} IEEE Symposium on Foundations of Computer Science ({Portland,} {OR)}, pages 74--78. IEEE, IEEE, 1985.
82. Christos H. Papadimitriou and David Wolfe. The complexity of facets resolved. J. Comput. Syst. Sci., 37:2--13, 1988.

IV Applications and Selected Polyhedra

previous section        next section        top

83. A. Altshuler and M.A. Perles . Quotient polytopes of cyclic polytopes. {Part I}: Structure and characterization. Israel Journal of Mathematics, 36(2):97--125, 1980.
A quotient polytope is a polytope arrived at by taking repeated vertex figures. The authors characterize the quotients of cyclic polytopes, and show that every simplicial polytope with $d+3$ vertices can arise as a quotient of a cyclic polytope
cyclic
84. Franz Aurenhammer . Power diagrams: properties, algorithms, and applications. SIAM Journal on Computing, 16(1):79--96, 1987.
85. David Avis. On the extreme rays of the metric cone. Canadian Journal of Mathematics, 32:126--144, 1980.
86. David Avis. Generating rooted triangulations without repetitions. Algorithmica, 16:618--632, 1996.
Describes a technique to enumerate $3$-connected planar triangulations, or equivalantly simplicial $3$-polytopes
enumeration, 3-polytope, simplicial, triangulation
87. David Avis and Antoine Deza . Solitaire cones. manuscript in preparation, October 1995.
application
88. David Avis and Michel Marie Deza . The cut cone, $l_1$ embeddability, complexity and multicommodity flows. Networks, 21:596--617, 1991.
application
cut, metric
89. David Avis and Mutt . All facets of the six points Hamming cone. European Journal of Combinatorics, 10:309--312, 1989.
hamming
90. K. B{\"o}r{\"o}czky . On an extremum property of the regular simplex in $S\sp d$. In Intuitive geometry (Si\'ofok, 1985), volume 48 of Colloq. Math. Soc. J\'anos Bolyai, pages 117--121. North-Holland, Amsterdam, 1987.
metric
91. Braams. Polytopes from quantum chemistry. private communication, 1995.
92. K.Q. Brown. Voronoi diagrams from convex hulls. Information Processing Letters, 9:223--228, 1979.
Voronoi diagram
93. G. Ceder, G.D. Garbulsky, David Avis, and Komei Fukuda . Ground states of a ternary lattice model with nearest and next-nearest neighbor interactions. Physical Review B, 49:1--7, 1994.
Uses a linear optimization model with unknown objective function to model the ground states (crystal structure) of alloys.
application
94. John Conway. Purging pegs properly. In Elwyn R. Berlekamp , editor, Winning Ways, for your mathematical plays, volume 2, chapter 23. Academic Press, 1982.
Describes a polyhedral approach to deciding whether there is a legal sequence of moves between two peg solitaire board configurations.
application
95. Antoine Deza, M. Deza, and Komei Fukuda . On skeletons, diameters and volumes of metric polyhedra. In Combinatorics and computer science (Brest, 1995), volume 1120 of Lecture Notes in Computer Science, pages 112--128. Springer-Verlag, Berlin, 1996.
ridge-diameter
96. Antoine Deza and Michel Marie Deza . The ridge graph of the metric polytope and some relatives. In Bistztriczky et al. [144].
Proves, among other things, that the ridge graph of the metric polytope has diameter 2.
ridge-diameter
metric
97. Michel Marie Deza . Matrices de formes quadratiques non n\'egatives pour des arguments binaires. Comptes rendues de l'Acad\'emie des Sciences de Paris, 277:873--875, 1973.
On the cut polytope.
cut
98. Michel Marie Deza and Monique Laurent . Facets for the cut cone I. Mathematical Programming, 56(2):121--160, 1992.
family description
cut
99. Michel Marie Deza and Monique Laurent . Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1997.
cut, metric, book
100. R. Euler and H. {Le Verge} . Complete linear descriptions of small asymetric travelling salesman polytopes. Discrete Applied Mathematics, 62:193--208, 1995.
Uses a version of Chernikova's algorithm [24] to compute the facet descriptions of the asymetric travelling salesman polytopes on 5 and 6 nodes. The 6 node polytope has 319015 facet defining inequalities and 11 equalities.
facet-enumeration, application
atsp
101. V. P. Grishukin. Computing extreme rays of the metric cone for seven points. European Journal of Combinatorics, 13:153--165, 1992.
metric
102. Branko Gr{\"u}nbaum and V. P. Sreedharan . An enumeration of simplicial 4-polytopes with 8 vertices. J. Combinatorial Theory, 2:437--465, 1967.
enumeration, 4-polytope, simplicial
103. James P. Ignizio and Tom M. Cavalier . Linear Programming. In {\em Prentice Hall International Series in Industrial and Systems Engineering\/} [76], 1994. Part III.
A general reference on multiobjective optimization.
104. T.P. Kirkman. On the enumeration of $x$-hedra having triedal summits and an $(x-1)$-gonal base. Philos. Trans. Royal Soc. London Ser. A, 146:399--411, 1856.
Characterizes those 3-polytopes containing a facet that is adjacent to every other facet
105. M. Lomonosov. Combinatorial approaches to multiflow problems. Discrete Applied Mathematics, 11:1--93, 1985.
Application of the metric polytope to multicommodity flows.
application
metric
106. Michael V. Mannino and Murlidar V. Koushik. The cost minimizing inverse classification problem: a genetic algorithm approach. Manuscript. Dept. of Management Science Box 353200 University of Washington Seattle.
Uses reverse search [7, 58] to compute Voronoi diagrams.
107. F. R{\"o}hrdanz, H. Mosemann, and F.M. Wahl. A high level system for generating and evaluating stable robot assembly sequences. Technical report, Technische Universit{\"a}t Braunschweig, Informatik, Robotik und Proze\S{}informatik, 1997. http://www.cs.tu-bs.de/rob/projects/highlap/technical_report.html
Uses reverse search (see [7, 58]) to test the frictional stability of an assembly
108. B.G. Romanchuk. A polytope based algorithm to compute regions of attraction: planar case. Technical Report CUED/F-INFENG/TR. 228, University of Cambridge Dept. of Engineering, 1995.
The use of vertex enumeration in nonlinear dynamical systems.
109. Paul Snow. Improved posterior probability estimates from prior and conditional linear constraint systems. IEEE Transactions on Systems, Man, and Cybernetics, 21(2):464--469, 1991.
Imprecise probabilities are modelled as linear constraints.
110. Marek Teichmann. Probabilistic algorithms for efficient grasping and fixturing. Manuscript. Courant Institute, N.Y.U., November 1995.
Using convex hulls to compute the maximum force resistable by a set of fingers grasping an object.
111. Branko Gr{\"u}nbaum and Theodore S. Motzkin. The number of hexagons and the simplicity of geodesics on certain polyhedra. Canadian Journal of Mathematics, 15:744--751, 1963.
More on realizable $p$-vectors. See also [155]
p-vector
112. Stephen B. Maurer . Matrix generalizations of some theorems on trees, cycles and cocycles in graphs. Siam J. Appl. Math, 30(1):143--148, Jan. 1986.
Generalizes the matrix tree theorem to count bases of unimodular matrices in time polynomial in the size of the matrix.

V Triangulation, Perturbation, and Degeneracy

previous section        next section        top
113. Paul Armand. Comportement combinatoire des poly\edres perturb\'es en programmation lin\'eaire. Comptes rendues de l'Acad\'emie des Sciences de Paris, 315:241--244, 1992.
Abstract of [114]. En fran\ccais.
perturbation
114. Paul Armand. Bounds on the number of vertices of polyhedra. Annals of Operations Research, 47:249--269, 1993.
The maximum number of broken vertices'' resulting from a single vertex $v$ of a perturbed $d$ polytope is at most $${{\lfloor d/2 \rfloor+ \sigma } \choose \sigma} + {{\lfloor d/2-1 \rfloor+ \sigma } \choose \sigma} -\sigma-1$$ where $\sigma$ is the number of extra'' constraints for $v$ and this bound is achieved.
perturbation
115. Margaret M. Bayer . Equidecomposable and weakly neighborly polytopes. Israel Journal of Mathematics, 81:301--320, 1993.
A polytope is called {\em equidecomposable\/} if every triangulation has the same $f$-vector. A polytope is called {\em weakly neighbourly\/} if every $k+1$ vertices are contained in a face of dimension at most $2k$, $0\leq k\leq{}d$. One result of this paper is that weakly neighbourly polytopes are equidecomposable
triangulation, equidecomposable, weakly neighbourly
prodsimplex
116. Louis J. Billera, R. Cushman, and J.A. Sanders. The Stanley decomposition of the harmonic oscillator. Proceedings of the Netherlands Mathematical Society, 50(4):375--393, December 1988.
Contains a proof that every triangulation of $T_s\timesT_t$ requires exactly ${s+t \choose t}$ simplicies.
triangulation, lower bounds
prodsimplex
117. Louis J. Billera, Paul Filliman, and Bernd Sturmfels. Constructions and complexity of secondary polytopes. Advances in Mathematics, 83:155--179, 1990.
triangulation
118. Louis J. Billera and Beth Spellman Munson. Triangulations of oriented matroids and convex polytopes. SIAM Journal of Algebraic Discrete Methods, 5(4):515--525, 1984.
A triangulation of an oriented matroid in terms of lifts'' is defined. This triangulation induces a triangulation of the corresponding convex polytope in the representable case.
triangulation, oriented-matroid
119. Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete and Computational Geometry, 9:145--158, 1993.
A cutting is a simplicial decomposition of $R^d$ such that simplex is intersected only by a constant fraction $n/r$ of the $n$ input hyperplanes. The author shows how to compute such a decomposition of size $O(r^d)$ in time $O(n r^{d-1})$.
triangulation, fixed-dimension
120. {Jes\'us} de Loera . Triangulations of Polytopes and Computational Algebra. PhD thesis, Cornell, 1995.
triangulation
121. {Jes\'us} de Loera, Bernd Sturmfels, and Rekha A. Thomas. Gr{\"o}bner bases and triangulations of the second hypersimplex. Combinatorica, 15(3):409--424, 1995.
triangulation
hypersimplex
122. H. G. Eggleston, Branko Gr{\"u}nbaum, and Victor Klee. Some semicontinuity theorems for convex polytopes and cell-complexes. Comment. Math. Helvet., 39:165--188, 1964.
Characterizes the combinatorial structure of polytopes resulting from pulling''
f-vector, pulling, perturbation
123. Tomas Gal. Degeneracy graphs: theory and application. an updated survey. Annals of Operations Research, 47:81--105, 1993.
A survey of the O.R. literature concerning the graph theoretic structure of the basis graph of a single vertex of a convex polyhedron
perturbation, degeneracy
124. Tomas Gal. Selected bibliography on degeneracy. Annals of Operations Research, 47:1--8, 1993.
A briefly annoted bibliography on linear programming degeneracy.
perturbation, degeneracy
125. I.M. Gel'fand, M.M. Kapranov, and A.V. Zelevinsky. Discriminants, resultants, and multidimensional determinants. Mathematics: theory \& applications. Birkhauser, Boston, 1994.
Also contains a proof that every triangulation of $T_s\timesT_t$ requires exactly ${s+t \choose t}$ simplicies.
126. M. Haiman. A simple and relatively efficient triangulation of the $n$-cube. Discrete and Computational Geometry, 6(4):287--289, 1991.
Includes a brief description of the volume based lower bound of $\Omega(\sqrtn!)$ lower bound for triangulations of a cube. Contains a volume based proof for the fact that every triangulation of $T_k \times T_l$ requires exactly $\binom{k+l}l$ maximal simplices.
triangulation
cube, prodsimplex
127. Matthew Hudelson, Victor Klee, and David Larman. Largest $j$-simplicies in $d$-cubes: some relatives of the Hadamard maximum determinant problem. Linear Algebra and Its Applications, 241:519--598, 1996.
128. Robert B. Hughes and Micheal R. Anderson . Simplexity of the cube. Discrete Mathematics, 158:99--150, 1996.
129. James P. Ignizio and Tom M. Cavalier . Linear Programming, pages 118--122. In {\em Prentice Hall International Series in Industrial and Systems Engineering\/} [76], 1994.
Description of lexicographic ratio testing
130. Victor Klee. On the number of vertices of a convex polytope. Canadian Journal of Mathematics, 16:701--720, 1964.
Develops the notion of pushing'' a vertex of a polytope
pushing, f-vector, perturbation
131. Carl W. Lee. Regular triangulations of convex polytopes. In The Victor Klee Festschrift, volume 4 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 443--456. American Mathematical Society, 1991.
triangulation
132. Nimrod Megiddo and R. Chandrasekaran . On the $\epsilon$-perturbation method for avoiding degeneracy. Operations Research Letters, 8:305--308, 1989.
133. Raimund Seidel. The nature and meaning of perturbations in geometric computing. To appear Discrete and Computational Geometry, 1996.
134. Richard P. Stanley . Decompositions of rational polytopes. In Combinatorial mathematics, optimal designs and their applications, volume 6 of Annals of Discrete Mathematics, pages 333--342. North-Holland, 1980.
Gives a characterization of when an ordering of the vertices of a polytope is compressed, i.e. every simplex in the induced triangulation has volume $1/n!$ (Theorem 2.3).
135. Richard P. Stanley . Subdivisions and local $h$-vectors. Journal of the American Mathematical Society, 5(4):805--851, October 1992.
A general theory of the $f$-vectors of triangulations. Let $\Gamma$ be a triangulation of a rational polytope $P$. $f_d(\Gamma) \geq \sum_{i=1}^dh_i$ (Corollary 7.11)
136. C-K Yap. Symbolic treatment of geometric dependancies. J. Symbolic Computation, 10:349--370, 1990.
degeneracy, perturbation
137. Peter Z{\"o}rnig. A theory of degeneracy graphs. Annals of Operations Research, 47:541--557, 1993.
A characterization of degeneracy graphs (see [123] for a survey) in terms of finite set systems. Let $G(\sigma,n)$ be a degeneracy graph of a vertex with $\sigma$ extra'' constraints in $n$ dimensions. The following are proved:
• ${\rm diameter}(G(\sigma,n)) \leq \min (\sigma, n)$
• the number of bases of a vertex can be computed if the representation system'' for the graph is known.
diameter, degeneracy

VI Related Theory

previous section        top

138. Oswin Aichholzer. 0/1-polytopes: Remote computing services via e-mail. E-mail accessible database, 1999. http://www.cis.tu-graz.ac.at/igi/oaich/info01poly.html
139. David W. Barnette . The minimum number of vertices of a simple polytope. Israel Journal of Mathematics, 10:121--125, 1971.
The lower bound theorem. A simple $d$-polytope with $m$ facets has at least $\beta(d,m) = (m-d)(d-1)+2$ vertices. See also [140]
f-vector, combinatorial structure
140. David W. Barnette . A proof of the lower bound conjecture for convex polytopes. Pacific Journal of Mathematics, 46:349--354, 1973.
Lower Bound Theorem, truncation polytope, stacked polytope, combinatorial structure
141. Margaret M. Bayer and Carl W. Lee . Combinatorial aspects of convex polytopes. In P.M. Gruber and J.M. Wills , editors, Handbook of Convex Geometry, volume A, chapter 2.3, pages 485--534. North Holland, New York, NY, 1993.
A survey of results up to about 1993. Includes a large section on results using algebraic geometry.
reference, combinatorial structure
142. Russell V. Benson . Euclidean Geometry and Convexity. McGraw-Hill, 1966.
convexity, metric, linear-algebra, book
143. Louis J. Billera and Carl W. Lee . A proof of the sufficency of {McMullen's} conditions for $f$-vectors of simplicial convex polytopes. Journal of Combinatorial Theory A, 31:237--255, 1981.
f-vector, stacked polytope, simplicial, combinatorial structure
144. T. Bistztriczky, P. McMullen, R. Schneider, and R. Ivic Weiss, editors. Polytopes: abstract, convex and computational (Scarborough, ON, 1993), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 440. Kluwer Acad. Publ., Dordrecht, 1994.
reference, metric, symmetry, combinatorial structure
145. Gerd Blind and Roswitha Blind . Convex polytopes without triangular faces. Israel Journal of Mathematics, 71:129--134, 1990.
The authors show that for a $d$-polytope $P$ without a triangular $2$-face, $f_k(P) \geq f_k(H_d)$ where $H_d$ is the $d$-dimensional hypercube.
triangle-free, combinatorial structure
cube
146. David Bremner and Victor Klee . Inner diagonals of convex polytopes. Journal of Combinatorial Theory A, 1998. accepted July 1998. http://www.cs.unb.ca/~bremner/research/papers/bk-idcp-99.ps.gz
diagonal, 2-neighbourly, combinatorial structure
147. Arno Br{\o}ndsted . Introduction to Convex Polytopes. Springer-Verlag, 1981.
Introductory text. Proves the upper and lower bound theorems starting from affine and convex combinations.
book, combinatorial structure
148. E. Jucovi\v c. On polyhedral realizability of certain sequences. Canad. Math. Bull., 12:31--39, 1969.
More on realizable $p$-vectors. See also [155]
p-vector, 3-polytope
149. C. Carath\'eodory . {\"Uber die Variabilit\"atsbereich der Fourierschen Konstanten}. Rend. Circ. Palermo, 32:193--217, 1911.
Describes cyclic polytopes
cyclic, neighbourly
cyclic
150. R. Chandrasekaran, Santosh N. Kabadi, and Katta G. Murty. Some NP-complete problems in linear programming. Operations Research Letters, 1(3):101--104, July 1982.
Checking a polytope for degeneracy is NP-Complete. So is checking whether there is a feasible solution with a specific objective value.
NP-Complete, degeneracy, linear programming
151. George B. Dantzig and B. Curtis Eaves . Fourier--motzkin elimination and its dual. Journal of Combinatorial Theory A, 14:288--297, 1973.
Fourier-Motzkin elimination
152. Antoine Deza. On a lower bound for general convex polytopes. Mathematica Japonicae, 40(2):371--380, 1994.
combinatorial structure, f-vector
153. Antoine Deza and Komei Fukuda . {McMullen's} conditions and some lower bounds for general convex polytopes. Geometriae Dedicata, 53:165--173, 1994.
f-vector, combinatorial structure
154. B.C. Eaves and R.M. Freund . Optimal scaling of balls and polyhedra. Mathematical Programming, 23:138--147, 1982.
Reduces several containment problems to linear programming
containment
155. V. Eberhard. Zur Morphologie der Polyeder. Teubner, Leipzig, 1891.
Shows that for each sequence of nonnegative integers $p_i$, satisfying $\sum (6-i)p_i = 12$, there is some value for $p_6$ such that the $p_i$s form the degree seqence of a simplicial $3$-polytope, or equivalently $p_i$ is the number of $i$-gonal faces of some simple $3$-polytope. A simpler proof is contained in [161].
p-vector, 3-polytope
156. Herbert Edelsbrunner . Algorithms in Combinatorial Geometry. Number 10 in EATCS Monographs on Th. Comp. Sci. Springer-Verlag, 1987.
computational geometry, reference
157. J. C. Fisher. An existence theorem for simple convex polyhedra. Discrete Math., 7:75--97, 1974.
More on realizable $p$-vectors. See also [155]
p-vector
158. Robert M. Freund and James B. Orlin . On the complexity of four polyhedral containment problems. Mathematical Programming, 33:139--145, 1985.
The authors show that a problem closely related to polytope verification is NP-complete. Specifically, given a polyhedron $P=\{ Ax \leq b\}$ and set of points and extreme rays $Y$, is ${\rm CH}(Y)$ strictly contained in $P$.
NP-Complete, containment
159. David Gale. Neighborly and cyclic polytopes. In Victor Klee , editor, Proceedings of the 7th Symposium on Pure Mathematics, 1961.
cyclic, neighbourly
160. A. Ghouila-Houri. Caract\'erisation des matrices totalment unimodulairs. Comptes Rendus Hebdomadaires des S\'eances de l'Acad\'emie des Sciences (Paris), 254:1192--1194, 1962.
161. Branko Gr{\"u}nbaum . Convex Polytopes, volume XVI of Pure and Applied Mathematics. Interscience, London, 1967.
162. Branko Gr{\"u}nbaum . Polytopal graphs, volume 12 of MAA Studies in Mathematics, pages 201--224. Mathematical Association of America, 1975.
More on realizable $p$-vectors. See also [155]
p-vector, 3-polytope
163. Harris Hancock. Development of the Minkowski Geometry of Numbers, chapter 33, pages 100--106. Macmillan, New York, NY, 1939. English translation/paraphrase of [181].
164. M. Henk, J. Richter-Gebert, and G. M. Ziegler. Basic properties of convex polytopes. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 13, pages 243--270. CRC Press LLC, 1997.
165. Fred B. Holt and Victor Klee . Many polytopes meeting the conjectured Hirsch bound. To appear., 1996.
diameter
166. Fred B. Holt and Victor Klee . Counterexamples to the strong $d$-step conjecture for $d\geq 5$. Discrete and Computational Geometry, 1998. To appear.
diameter
167. S. Jendrol'. On the face-vectors of trivalent convex polyhedra. Math. Slovaca, 33:165--180, 1983.
More on realizable $p$-vectors. See also [155]
3-polytope, p-vector
168. Gil Kalai. Rigidity and the lower bound theorem i. Invent. Math., 88:125--151, 1987.
Uses the theory of rigity of frameworks to provide another proof of the Lower Bound Theorem [139], and generalizes to triangulated manifolds. Also shows that $g_2(P) = f_1(P) - ( dv - \binom{d+1}2) + \sum_{k>3} (k-3) p_k(P)$ is non-negative, where $p_k(P)$ denotes the number of $k$-gonal $2$-faces of $P$.
g-vector, p-vector, rigidity, Lower Bound Theorem
169. Gil Kalai. The number of faces of centrally symmetric convex polytopes. Graphs and Combinatorics, 5:389--391, 1989. Research Problem.
centrally symmetric, Lower Bound Theorem
cube
170. Gil Kalai. Some aspects of the combinatorial theory of convex polytopes, pages 205--229. In Bistztriczky et al. [144], 1993.
Contains some results related to [168]
g-vector, p-vector, rigidity, Lower Bound Theorem
171. Victor Klee. Polytope pairs and their relationship to linear programming. Acta Math., 133:1--25, 1974.
Shows that there exists pairs $(P,F)$ where $P$ is a convex polytope and $F$ is a facet of $P$ such that numbers of vertices close to the extremes of [139, 177] are independently achieved for $P$ and $P\setminusF$. Furthmore, these bounds are achieved for $(P,F)$ where $F$ intersects every other facet of $P$ (a Kirkman pair'', see [104]).
Lower Bound Theorem, polytope pairs
172. Victor Klee. A $d$-pseudomanifold with $f_0$ vertices has at least $df_0-(d-1)(d+2)$ $d$-simplices. Houston Journal of Mathematics, 1:81--86, 1975.
Lower Bound Theorem, pseudomanifold
173. Victor Klee and Peter Kleinschmidt . The $d$-step conjecture and its relatives. Mathematics of Operations Research, 12(4):718--755, November 1987.
diameter
Q4
174. Victor Klee and David W. Walkup . The $d$-step conjecture for polyhedra of dimension $d<6$. Acta Mathematica, 133:53--78, 1967.
diameter
175. Ulrich H. Kortenkamp, J{\"u}rgen Richter-Gebert, Aravamuthan Sarangarajan, and G{\"u}nter M. Ziegler . Extremal properties of 0/1-polytopes. Discrete and Computational Geometry, 4(16), 1997.
zero-one
176. Peter Mani. Inner illumination of convex polytopes. Comment. Math. Helv., 49:65--73, 1974.
diagonal, illumination
177. Peter McMullen. The maximal number of faces of a convex polytope. Mathematika, 17:179--184, 1970.
The upper bound theorem: a convex $d$-polytope with $m$ facets has at most \begindisplaymath \gamma(d,m) = { m- \lfloor(d+1)/2\rfloor \choose m-d } + {m- \lfloor{(d+2)/2}\rfloor \choose m-d} \enddisplaymath vertices.
178. Peter McMullen. The minimum number of facets of a convex polytope. Journal of the London Mathematical Society, 3(2):350--354, 1971.
179. Peter McMullen. The number of faces of simplicial polytopes. Israel Journal of Mathematics, 9:559--570, 1971.
180. Peter McMullen and G. C. Shephard . Convex polytopes and the Upper Bound Conjecture. Cambridge University Press, Cambridge, 1971.
181. Hermann Minkowski . Geometrie der Zahlen, chapter 19, pages 39--45. Teubner, Leipzig, 1910. English translation/paraphrase in [163].
The following theorems are proved (all systems under consideration are homogeneous):
1. Every basic solution of a system of inequalities is extreme.
2. If there is a solution of a system of inequalities, there is a basic solution.
3. Every solution is a positive combination of extreme solutions.
Algorithms are provided to compute the redundant constraints in a system, and to compute the extreme solutions of a system by considering each linearly independent set of constraints.
vertex-enumeration, redundancy-removal
182. Theodore S. Motzkin . Comonotone curves and polytopes. Bulletin of the American Mathematical Society, 63(35), 1957. Abstract 111.
Conjectures the Upper Bound Theorem (see [177])
Upper Bound Theorem
cyclic
183. James A. Murtha and Earl R. Willard . Linear Algebra and Geometry. Holt Rinehart and Winston, New York, 1969.
184. Nemhauser and Wolsey . Integer Programming. Wiley-Interscience, 1988.
185. J{\"u}rgen Richter-Gebert . Realization Spaces of 4-polytopes are universal. Habilitationsschrift, Technishe Universit{\"a}t Berlin, 1995.
oriented matroid, 4-polytope, realization space
186. Moishe Rosenfeld. Inner illumination of convex polytopes. Elemente Math., 30:27--28, 1975.
diagonal, illumination
187. J.-P. Roudneff. An inequality for $3$-polytopes. J. Combin. Theory B, 42:156--166, 1987.
More on realizable $p$-vectors. See also [155]
p-vector, 3-polytope
188. H.L. Royden. Real Analysis. MacMillan, 1968.
reference
189. Richard P. Stanley . The number faces of a simplicial convex polytope. Advances in Mathematics, 35:236--238, 1980.
190. Richard P. Stanley . Generalized $h$-vectors, intersection cohomology of toric varieties,. In Commutative Algebra and Combinatorics, pages 187--213. Kinokuniya, Tokyo and North Holland Amsterdam/New York, 1987.
Proves the nonnegativity of $g_2$ for rational polytopes.
g-vector
191. E. Steinitz and H. Rademacher . Vorlesungen {\"uber} die Theorie der Polyeder. Springer, Berlin, 1934.
The famous Steinitz's Theorem''
3-polytope
192. L. Fejes T\'oth. Regular Figures. McMillan/Pergamon, 1964.
193. Frederick A. Valentine . Convex Sets. McGraw-Hill Series in Higher Mathematics. McGraw-Hill, 1964.
194. B. von Stengel. New maximal numbers of equilibria in bimatrix games. Discrete Comp. Geom., 29, 1999. to appear.
diagonals
195. W. Whiteley. Infinitesimally rigid polyhedra i. statics of frameworks. Trans. Amer. Math. Soc., 285:431--465, 1984.
rigidity
196. G{\"u}nter M. Ziegler . Lectures on Polytopes. Graduate Texts in Mathematics. Springer-Verlag, 1994.
Modern text on convex polytopes. Emphasis on combinatorial techniques such as Schlegel diagrams oriented matroids, Gale diagrams and shellability.
reference, combinatorial structure
197. Artur Andrzejak and Komei Fukuda . Optimization of $k$-set polytopes and efficient $k$-set enumeration. In Proceedings of the 6th International Workshop on Algorithms and Data Structures, volume 1663 of Lecture Notes on Computer Science, pages 1--12. Springer-Verlag, 1999.
198. Dave Bayer and Bernd Sturmfels . Cellular resolutions of monomial modules. Journal F\"r die Reine und Angewandte Mathematik, 502:123--140, 1998.
Discusses the `exponent polytopes''.
199. Pey-Chun Chen, Pierre Hansen, Brigitte Jaumard, and Hoang Tuy. Solution of the multisource Weber and conditional Weber problems by d.-c. programming. Oper. Res., 46(4):548--562, 1998.
Uses vertex enumeration to solve generalized versions of the Weber Problem (a facility location problem)
200. J{\"u}rgen Richter-Gebert . Realization Spaces of Polytopes, volume 1643 of Lecture Notes in Mathematics. Springer-Verlag, 1996.