UNB/ CS/ David Bremner/ research/ polybib/ bibliography

1 Algorithms

   [1.1] N. Yu. Zolotykh. New modification of the double description method for constructing the skeleton of a polyhedral cone. Computational mathematics and mathematical physics, 52(1):146–156, 2012. http://www.springerlink.com/content/64100113317024g6/.

   [1.2] 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 [1.2]). The paper also details an optimization for the case when a variable occurs in exactly one constraint.

   [1.3] Garret Swart. Finding the convex hull facet by facet. Journal of Algorithms, :17–48, 1985.

Gives an analysis of Chand and Kapur’s dual pivoting algorithm [1.39]. Contains a modification of [1.39] that computes the face lattice in time polynomial in the input and output size.

   [1.4] 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 [?].

   [1.5] William Mott Stewart. Efficient incremental construction of convex hulls from spherical distributions in higher dimensions. University of New Brunswick. 1992.

The incremental construction of convex hulls is investigated. Given a set of n points S in d in general position, a data structure is given and an algorithm implemented to add a point to an existing convex hull in Θ(d3) expected time in the number of new facets created. Start of author abstract. See also [1.50] for more on spherical distributions.

   [1.6] G.J. Silverman. Computational considerations in extreme point computation. 1971. Report 320-2649, IBM L.A. Research Center.

Tries to find a “G-path” Π s.t. every vertex is either on Π or adjacent to it.

   [1.7] Raimund Seidel. Constructing higher-dimensional convex hulls at logarithmic cost per face. 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.

   [1.8] Raimund Seidel. Output-size sensitive algorithms for constructive problems in computational geometry. Dept. Comput. Sci., Cornell Univ. 1986. Technical Report TR 86-784.

Uses shellings to get output sensitive time for fixed dimension and points in general position

   [1.9] Raimund Seidel. A convex hull algorithm optimal for point sets in even dimensions. University of British Columbia, Dept. of Computer Science. 1981. Report 81-14.

Achieves a time bound of O(nd∕2) in fixed even dimension d.

   [1.10] Günter Rote. Degenerate convex hulls in high dimensions without extra storage. 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.

   [1.11] 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

   [1.12] K.G. Murty. Solving the fixed charge problem by ranking the extreme points. Operations Research, 16:268–279, 1968.

According to [1.19]: uses the fact that if vertices are ordered in nondecreasing order by linear objective cx, then vk+1 must be adjacent to one of v1vk. 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

   [1.13] Theodore S. Motzkin, H. Raiffa, G.L. Thompson, and R. M. Thrall. The double description method. Contributions to the Theory of Games II, Annals of Math. Studies, 8:51–73, 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

   [1.14] Theodore S. Motzkin. Contributions to the theory of linear inequalites. Theodore S. Motzkin: Selected Papers, 1983.

   [1.15] Theodore S. Motzkin. Contributions to the theory of linear inequalites. Number 22 in RAND Corporaton Translations. Rand Corporation, 1952. English translation of [1.16]. Reprinted in [1.13].

   [1.16] Theodore S. Motzkin. Beiträge zur theorie der linearen ungleichungen. Universität Basel. 1933. Published in Jerusalem in 1936, English translation in  [1.141.13].

Sketches the double description method (i.e. successive intersection of halfspaces) in a proof of a generalization of a finite basis theorem of Minkowski ( 30). Gives a more complete description of the elimination procedure introduced by Fourier [1.28] ( 87).

   [1.17] Theodore S. Motzkin. Beiträge zur theorie der linearen ungleichungen. Universität Basel. 1933. Published in Jerusalem in 1936, English translation in  [1.141.13].

Sketches the double description method (i.e. successive intersection of halfspaces) in a proof of a generalization of a finite basis theorem of Minkowski ( 30). Gives a more complete description of the elimination procedure introduced by Fourier [1.28] ( 87).

   [1.18] 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.

   [1.19] Miroslav Maňas 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.

   [1.20] 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.

   [1.21] D.A. Kohler. Translation of a report by Fourier on his work on linear inequalities. Opsearch, 10:38–42, 1973. Translation of [1.28].

   [1.22] Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, and Vladimir Gurvich. Generating all vertices of a polyhedron is hard. Discrete and Computational Geometry, October 2007. http://dx.doi.org/10.1007/s00454-006-1259-6.

Abstract  We show that generating all negative cycles of a weighted graph is a hard enumeration problem, in both the directed and undirected cases. More precisely, given a family of negative (directed) cycles, it is an NP-complete problem to decide whether this family can be extended or there are no other negative (directed) cycles in the graph, implying that (directed) negative cycles cannot be generated in polynomial output time, unless P = NP. As a corollary, we solve in the negative two well-known generating problems from linear programming: (i) Given an infeasible system of linear inequalities, generating all minimal infeasible subsystems is hard. Yet, for generating maximal feasible subsystems the complexity remains open. (ii) Given a feasible system of linear inequalities, generating all vertices of the corresponding polyhedron is hard. Yet, in the case of bounded polyhedra the complexity remains open. Equivalently, the complexity of generating vertices and extreme rays of polyhedra remains open.

   [1.23] Peter Gritzmann and Victor Klee. On the complexity of some basic problems in computational convexity: II. Volume and mixed volumes. , :373–466, 1994.

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.

   [1.24] 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 f faces of a d-polytope with m facets and n vertices in time O(f2 min(m,n)). Requires vertex/facet incidence information as input.

   [1.25] Komei Fukuda and Alain Prodon. Double description method revisited. Combinatorics and computer science (Brest, 1995), Lecture Notes in Comput. Sci., 1120:91–111, 1996.

   [1.26] Komei Fukuda, Thomas M. Liebling, and Fran¸ 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 f faces of a polytope with m facets and n vertices in time O(fmL(m,n)) where L(m,n) is the amount of time necessary to solve an m by n linear program.

   [1.27] Komei Fukuda. Lecture notes: Combinatorics of mathematical programming and polyhedral geometry. 1993. EPFL, Lausaunne Switzerland.

   [1.28] Jean Baptiste Joseph Fourier. Œuvres de Fourier. Gauthier-Villars et Fils, Paris, 1890.

   [1.29] Jean Baptiste Joseph Fourier. Histoire de l’academie royale des sciences de l’institute de france. , 7:xlvii-lv, 1824. Reprinted in [1.27]. English translation in [1.20].

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

   [1.30] Jack Edmonds. Decomposition using Minkowski. 1991. Abstracts of the 14th International Symposium on Mathematical Programming, Amsterdam.

Gives a recursive procedure that given P = {xAx 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(md3), where m is the row size of A.

   [1.31] Herbert Edelsbrunner. Algorithms in combinatorial geometry. , EATCS Monographs on Th. Comp. Sci., Chapter 8.4, 10(10):147–158, 1987.

Description of the beneath and beyond method in d-dimensions. Written by Raimund Seidel. Achieves a time bound of O(nd∕2) in fixed even dimension d.

   [1.32] 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.

   [1.33] Martin E. Dyer. The complexity of vertex enumeration methods. Mathematics of Operations Research, 8(3):381–402, 1983.

Uses a result of Klee [?] 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

   [1.34] Kenneth L. Clarkson and Peter W. Shor. Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incremental. Proceedings of the 4th ACM Symposium on Computational Geometry, pages 12–17, 1988.

A randomized insertion algorithm. Uses triangulation.

   [1.35] Kenneth L. Clarkson. More output-sensitive geometric algorithms. Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pages 695–702, 1994. http://cm.bell-labs.com/who/clarkson/os/p.pdf.

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.

   [1.36] 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 [1.12], with the implementation simplifying assumption that the variables are non-negative.

   [1.37] 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 cdd [?].

   [1.38] 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(nd∕2) in fixed dimension d.

   [1.39] A. Charnes. The simplex method: Optimal set and degeneracy. An introduction to Linear Programming, Chapter VI, :62–70, 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.

   [1.40] 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 [1.2].

   [1.41] 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. Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, pages 282–291, 1995.

   [1.42] Timothy M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. 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.

   [1.43] Burdet C.–A. Generating all faces of a polyhedron. SIAM J. Appl. Math., 26:479-489, 1974.

   [1.44] E. Burger. üBer homogene lineare Ungleichungssysteme. Zeitschrift für Angewandte Mathematik und Mechanik, 36:135–139, 1956.

Contains a description of the double description method.

   [1.45] Adrian Brü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 lrs [?]

   [1.46] 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/profs/bremner/research/papers/bfm-pdmvf-98.ps.gz.

   [1.47] 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/profs/bremner/research/papers/b-ichan-98.ps.gz.

   [1.48] David Bremner. On the complexity of vertex and facet enumeration for convex polytopes. School of Computer Science, McGill University. 1997. http://www.cs.unb.ca/profs/bremner/research/papers/phd.

   [1.49] David Bremner. Incremental convex hull algorithms are not output sensitive. Proceedings of the International Symposium on Algorithms and Computation ’96, 1178:26–35, December 1996. http://www.cs.unb.ca/profs/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.

   [1.50] O. Bournez, O. Maler, and A. Pnueli. Orthogonal polyhedra: Representation and computation. Hybrid Systems: Computation and Control, LNCS 1569, 1999. http://www-verimag.imag.fr/~maler/Papers/griddy.pdf.

Author Abstract. 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.

   [1.51] 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. [1.21.39]) on random input. The claim is that for random input, redundant points need not be removed by preprocessing.

   [1.52] 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 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.

   [1.53] David Avis and Luc Devroye. Estimating the number of vertices of a polyhedron. Snapshots in Computational and Discrete Geometry, 3:179–190, 1994.

Uses reverse search [1.51] to estimate the number of feasible bases and vertices of a polytope.

   [1.54] David Avis and David Bremner. Large convex hull problems. Zeitschrift für Angewandte Mathematik und Mechanik, 87(3):179–182, July 1995. Special Issue: Proceedings of the Third International Congress on Industrial and Applied Mathematics.

   [1.55] David Avis and David Bremner. How good are convex hull algorithms? 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.

   [1.56] 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/profs/bremner/research/papers/abs-hgach-97.ps.gz.

   [1.57] Nancy M. Amato, Micheal T. Goodrich, and Edgar A. Ramos. Parallel algorithms for higher-dimensional convex hulls. 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(log n) time and O(n log n+nd∕2) work, where d is assumed to be constant. Uses a modified notion of cutting (see [4.19]) to decompose the space (rather than the input halfspaces) in order to do divide and conquer.

   [1.58] W. Altherr. An algorithm for enumerating the vertices of a convex polyhedron. Computing, 15:181–193, 1975.

2 Linear Programming

   [2.1] Alexander Schrijver. Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics. Wily-Interscience, New York, 1986.

   [2.2] Victor Klee and G.J. Minty. How good is the simplex method? Inequalities-III, :159–175, 1972.

Gave a class of skewed d-cubes for which the simplex method using the largest coefficent method visits all vertices

   [2.3] L.V. Kantorovich. My journey in science. Russian Math. Surveys, 42:233-270, 1987.

Discusses early work on the simplex type algorithms.

   [2.4] James P. Ignizio and Tom M. Cavalier. Linear Programming. Prentice Hall International Series in Industrial and Systems Engineering. Prentice Hall, 1994.

   [2.5] 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.] Notes by Seth Teller

   [2.6] 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.

   [2.7] George.B. Dantzig. Maximizing a linear function of variables subject to linear inequalities. Activity Analysis of Production and Allocation, :339–347, 1951.

   [2.8] George B. Dantzig, Alex Orden, and Philip Wolfe. The generalized simplex method for minimizing a linear form under linear inequality restraints. Pacific Journal of Mathematics, 5:183–195, 1955.

The canonical description of the simplex method using lexicographic pivoting.

   [2.9] Vašek Chvátal. Linear Programming. W. H. Freeman, New York, NY, 1983.

   [2.10] David Avis and Vašek Chvátal. Notes on Bland’s pivoting rule. Math. Programming Study, 8:24–34, 1978.

3 Applications and Selected Polyhedra

   [3.1] Marek Teichmann. Probabilistic algorithms for efficient grasping and fixturing. November 1995. Manuscript. Courant Institute, N.Y.U.

Using convex hulls to compute the maximum force resistable by a set of fingers grasping an object.

   [3.2] 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.

   [3.3] B.G. Romanchuk. A polytope based algorithm to compute regions of attraction: Planar case. 1995.

The use of vertex enumeration in nonlinear dynamical systems.

   [3.4] F. Röhrdanz, H. Mosemann, and F.M. Wahl. A high level system for generating and evaluating stable robot assembly sequences. 1997. http://doi.ieeecomputersociety.org/10.1109/IJSIS.1996.565061.

Uses reverse search (see [1.51?]) to test the frictional stability of an assembly

   [3.5] 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 [1.51?] to compute Voronoi diagrams.

   [3.6] M. Lomonosov. Combinatorial approaches to multiflow problems. Discrete Applied Mathematics, 11:1–93, 1985.

Application of the metric polytope to multicommodity flows.

   [3.7] 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

   [3.8] James P. Ignizio and Tom M. Cavalier. Linear Programming. Part III.

   [3.9] Branko Grünbaum and V. P. Sreedharan. An enumeration of simplicial 4-polytopes with 8 vertices. J. Combinatorial Theory, 2:437–465, 1967.

   [3.10] V. P. Grishukin. Computing extreme rays of the metric cone for seven points. European Journal of Combinatorics, 13:153–165, 1992.

   [3.11] 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 [1.35] 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.

   [3.12] Michel Marie Deza and Monique Laurent. Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1997.

   [3.13] Michel Marie Deza and Monique Laurent. Facets for the cut cone I. Mathematical Programming, 56(2):121–160, 1992.

   [3.14] Michel Marie Deza. Matrices de formes quadratiques non négatives pour des arguments binaires. Comptes rendues de l’Académie des Sciences de Paris, 277:873–875, 1973.

On the cut polytope.

   [3.15] Antoine Deza and Michel Marie Deza. The ridge graph of the metric polytope and some relatives. Polytopes: abstract, convex and computational (Scarborough, ON, 1993), 1994.

Proves, among other things, that the ridge graph of the metric polytope has diameter 2.

   [3.16] Antoine Deza, M. Deza, and Komei Fukuda. On skeletons, diameters and volumes of metric polyhedra. Combinatorics and computer science (Brest, 1995), Lecture Notes in Computer Science, 1120:112–128, 1996.

   [3.17] John Conway. Purging pegs properly. Winning Ways, for your mathematical plays, Chapter 23, 1982.

Describes a polyhedral approach to deciding whether there is a legal sequence of moves between two peg solitaire board configurations.

   [3.18] 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.

   [3.19] K.Q. Brown. Voronoi diagrams from convex hulls. Information Processing Letters, 9:223–228, 1979.

   [3.20] Braams. Polytopes from quantum chemistry. 1995. private communication.

   [3.21] K. Böröczky. On an extremum property of the regular simplex in Sd. Intuitive geometry (Siófok, 1985), Colloq. Math. Soc. János Bolyai, 48:117–121, 1987.

   [3.22] David Avis and Mutt. All facets of the six points Hamming cone. European Journal of Combinatorics, 10:309–312, 1989.

   [3.23] David Avis and Michel Marie Deza. The cut cone, l1 embeddability, complexity and multicommodity flows. Networks, 21:596-617, 1991.

   [3.24] David Avis and Antoine Deza. Solitaire cones. October 1995. manuscript in preparation.

   [3.25] 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

   [3.26] David Avis. On the extreme rays of the metric cone. Canadian Journal of Mathematics, 32:126–144, 1980.

   [3.27] Franz Aurenhammer. Power diagrams: Properties, algorithms, and applications. SIAM Journal on Computing, 16(1):79–96, 1987.

   [3.28] 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

4 Triangulations

   [4.1] Peter Zörnig. A theory of degeneracy graphs. Annals of Operations Research, 47:541–557, 1993.

A characterization of degeneracy graphs (see [4.14] for a survey) in terms of finite set systems. Let G(σ,n) be a degeneracy graph of a vertex with σ “extra” constraints in n dimensions. The following are proved:

  • diameter(G(σ,n)) min(σ,n)
  • the number of bases of a vertex can be computed if the “representation system” for the graph is known.

   [4.2] C-K Yap. Symbolic treatment of geometric dependancies. J. Symbolic Computation, 10:349–370, 1990.

   [4.3] 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 Γ be a triangulation of a rational polytope P. fd(Γ) i=1dh i (Corollary 7.11)

   [4.4] Richard P. Stanley. Decompositions of rational polytopes. Combinatorial mathematics, optimal designs and their applications, Annals of Discrete Mathematics, 6:333–342, 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).

   [4.5] Raimund Seidel. The nature and meaning of perturbations in geometric computing. 1996. To appear Discrete and Computational Geometry.

   [4.6] Nimrod Megiddo and R. Chandrasekaran. On the ϵ-perturbation method for avoiding degeneracy. Operations Research Letters, 8:305–308, 1989.

   [4.7] Carl W. Lee. Regular triangulations of convex polytopes. The Victor Klee Festschrift, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 4:443–456, 1991.

   [4.8] 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

   [4.9] James P. Ignizio and Tom M. Cavalier. Linear programming. , :118–122.

Description of lexicographic ratio testing

   [4.10] Robert B. Hughes and Micheal R. Anderson. Simplexity of the cube. Discrete Mathematics, 158:99–150, 1996.

   [4.11] 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.

   [4.12] 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 Ω(√ --
  n!) lower bound for triangulations of a cube. Contains a volume based proof for the fact that every triangulation of Tk × Tl requires exactly (k+l)
  l maximal simplices.

   [4.13] I.M. Gel’fand, M.M. Kapranov, and A.V. Zelevinsky. Discriminants, resultants, and multidimensional determinants. Mathematics: theory & applications. Birkhauser, Boston, 1994.

   [4.14] 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

   [4.15] Tomas Gal. Selected bibliography on degeneracy. Annals of Operations Research, 47:1–8, 1993.

A briefly annoted bibliography on linear programming degeneracy.

   [4.16] H. G. Eggleston, Branko Grü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”

   [4.17] Jesús de Loera, Bernd Sturmfels, and Rekha A. Thomas. Gröbner bases and triangulations of the second hypersimplex. Combinatorica, 15(3):409–424, 1995.

   [4.18] Jesús de Loera. Triangulations of polytopes and computational algebra. Cornell. 1995.

   [4.19] Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete and Computational Geometry, 9:145–158, 1993.

A cutting is a simplicial decomposition of Rd 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(rd) in time O(nrd-1).

   [4.20] 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.

   [4.21] Louis J. Billera, Paul Filliman, and Bernd Sturmfels. Constructions and complexity of secondary polytopes. Advances in Mathematics, 83:155-179, 1990.

   [4.22] 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 Ts × Tt requires exactly (s+t t ) simplicies.

   [4.23] Margaret M. Bayer. Equidecomposable and weakly neighborly polytopes. Israel Journal of Mathematics, 81:301–320, 1993.

A polytope is called equidecomposable if every triangulation has the same f-vector. A polytope is called weakly neighbourly if every k + 1 vertices are contained in a face of dimension at most 2k, 0 k d. One result of this paper is that weakly neighbourly polytopes are equidecomposable

   [4.24] 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

(          )    (              )
  ⌊d∕2⌋ + σ   +   ⌊d∕2 - 1⌋ + σ  -  σ - 1
      σ                 σ
where σ is the number of “extra” constraints for v and this bound is achieved.

   [4.25] Paul Armand. Comportement combinatoire des polyèdres perturbés en programmation linéaire. Comptes rendues de l’Académie des Sciences de Paris, 315:241–244, 1992.

Abstract of  [4.24]. En français.

5 Related Theory

   [5.1] Branko Grü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 [?]