Generated on Tue Jan 30 13:26:25 2001

Sections

  1. Algorithms
  2. Implementations
  3. Linear Programming
  4. Applications and Selected Polyhedra
  5. Triangulation, Perturbation, and Degeneracy
  6. Related Theory

Feedback

I Algorithms

next section        top
See also: 37, 59, 71, 96, 144, 150, 170, 171

  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].
    gift-wrapping, pivoting, facet-enumeration
  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.
    facet-enumeration, pivoting, gift-wrapping
  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
    See also: 4

  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
    See also: 45, 69

  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
    See also: 4, 10, 11, 30, 32, 33, 38

  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.
    Describes the Fourier--Motzkin Elimination technique. See also [31, 42, 60]
    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.