D. AVIS, D. BREMNER, AND R. SEIDEL, How good are convex hull
algorithms?, Comput. Geom., Vol. 7, No. 5-6, pp. 265-301, 1997.
[2]
D. AVIS AND K. FUKUDA, A pivoting algorithm for convex hull and
vertex enumeration of arrangements and polyhedra, Discrete Comput. Geom.,
Vol. 8, No. 3, pp. 295-313, 1992.
[3]
L. BABAI, Automorphism groups, isomorphism, reconstruction, in
Handbook of Combinatorics, R. L. Graham, M. Grötschel, and L. Lovász,
eds., Vol. 2, Elsevier (North-Holland), Amsterdam, 1995, pp. 1447-1540.
[4]
A. BELOW, J. A. DE LOERA, AND J. RICHTER-GEBERT, The
complexity of finding small triangulations of convex 3-polytopes.
Journal of Algorithms, to appear; arXiv:math.CO/0012177, 2000.
[5]
————, Finding minimal triangulations of convex
3-polytopes is NP-hard, in Proceedings of the 11th annual ACM-SIAM
symposium on Discrete algorithms, San Francisco, CA, USA, SIAM, Philadelphia,
pp. 65-66, 2000.
[6]
R. BLIND AND P. MANI-LEVITSKA, On puzzles and polytope
isomorphisms, Aequationes Math., Vol. 34, pp. 287-297, 1987.
[7]
J. BOKOWSKI AND B. STURMFELS, Computational Synthetic Geometry,
No. 1355 in Lecture Notes in Mathematics, Springer-Verlag, 1989.
[8]
D. BREMNER, K. FUKUDA, AND A. MARZETTA, Primal-dual methods for
vertex and facet enumeration, Discrete Comput. Geom., Vol. 20, No. 3,
pp. 333-357, 1998.
[9]
T. M. CHAN, Output-sensitive results on convex hulls, extreme
points, and related problems, Discrete Comput. Geom., Vol. 16, No. 4,
pp. 369-387, 1996.
[10]
D. R. CHAND AND S. S. KAPUR, An algorithm for convex polytopes,
J. Assoc. Comput. Mach., Vol. 17, No. 78-86, 1970.
[11]
R. CHANDRASEKARAN, S. N. KABADI, AND K. G. MURTY, Some
NP-complete problems in linear programming, Oper. Res. Lett., Vol. 1,
No. 3, pp. 101-104, 1982.
[12]
B. CHAZELLE, An optimal convex hull algorithm in any fixed
dimension, Discrete Comput. Geom., Vol. 10, No. 4, pp. 377-409, 1993.
[13]
G. DANARAJ AND V. KLEE, A representation of 2-dimensional
pseudomanifolds and its use in the design of a linear-time shelling
algorithm., Ann. Discrete Math., Vol. 2, pp. 53-63, 1978.
[14]
M. E. DYER, The complexity of vertex enumeration methods, Math.
Oper. Res, Vol. 8, pp. 381-402, 1983.
[15]
M. E. DYER AND A. M. FRIEZE, On the complexity of computing the
volume of a polyhedron., SIAM J. Comput., Vol. 17, No. 5, pp. 967-974,
1988.
[16]
M. E. DYER, A. M. FRIEZE, AND R. KANNAN, A random
polynomial-time algorithm for approximating the volume of convex bodies.,
J. Assoc. Comput. Mach., Vol. 38, No. 1, pp. 1-17, 1991.
[17]
B. C. EAVES AND R. M. FREUND, Optimal scaling of balls and
polyhedra, Math. Program., Vol. 23, pp. 138-147, 1982.
[18]
J. EDMONDS, Paths, trees, and flowers, Can. J. Math., Vol. 17,
pp. 449-467, 1965.
[19]
J. ERICKSON, New lower bounds for convex hull problems in odd
dimensions, SIAM J. Comput., Vol. 28, No. 4, pp. 1198-1214, 1999.
[20]
R. M. FREUND AND J. B. ORLIN, On the complexity of four
polyhedral set containment problems, Math. Program., Vol. 33, pp. 139-145,
1985.
[21]
A. M. FRIEZE AND S.-H. TENG, On the complexity of computing the
diameter of a polytope, Comput. Complexity, Vol. 4, pp. 207-219, 1994.
[22]
K. FUKUDA, T. M. LIEBLING, AND F. MARGOT, Analysis of backtrack
algorithms for listing all vertices and all faces of a convex polyhedron,
Comput. Geom., Vol. 8, pp. 1-12, 1997.
[23]
M. R. GAREY AND D. S. JOHNSON, Computers and Intractability: A
Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San
Francisco, 1979.
[24]
B. GÄRTNER, The random facet simplex algorithm on
combinatorial cubes.
Manuscript, February 2001.
E. GAWRILOW AND M. JOSWIG, polymake: A framework for
analyzing convex polytopes, in Polytopes -- Combinatorics and Computation,
G. Kalai and G. M. Ziegler, eds., Birkhäuser, 2000, pp. 43-74.
[27]
————, polymake: an approach to modular
software design in computational geometry, in Proc. 17th ACM Ann. Symp.
Comput. Geom., pp. 222-231, 2001.
[28]
P. GRITZMANN, V. KLEE, AND D. LARMAN, Largest j-simplices in
n-polytopes, Discrete Comput. Geom., Vol. 13, pp. 477-515, 1995.
[29]
J. E. HOPCROFT AND R. E. TARJAN, Dividing a graph into
triconnected components, SIAM J. Comput., Vol. 2, pp. 135-158, 1973.
[30]
————, Efficient planarity testing, J. Assoc.
Comput. Mach., Vol. 21, pp. 549-568, 1974.
[31]
C. S. ILIOPOULOS, Worst-case complexity bounds on algorithms for
computing the canonical structure of finite Abelian groups and the
Hermite and Smith normal forms of an integer matrix, SIAM J. Comput.,
Vol. 18, No. 4, pp. 658-669, 1989.
[32]
M. JOSWIG, V. KAIBEL, AND F. KÖRNER, On the k-systems of a
simple polytope, Isr. J. Math., Vol. 129, pp. 109-118, 2002.
[33]
V. KAIBEL AND M. E. PFETSCH, Computing the face lattice of a
polytope from its vertex-facet incidences, Comput. Geom., Vol. 23, No. 3,
pp. 281-290, 2002.
[34]
V. KAIBEL AND A. SCHWARTZ, On the complexity of isomorphism
problems related to polytopes, tech. report, TU Berlin, 2001.
Submitted.
[35]
G. KALAI, A simple way to tell a simple polytope from its
graph, J. Comb. Theory, Ser. A, Vol. 49, No. 2, pp. 381-383, 1988.
[36]
G. KALAI, A subexponential randomized simplex algorithm, in
Proc. 24th Ann. ACM Symp. Theory Comput., Victoria, pp. 475-482, 1992, ACM
Press.
[37]
N. KARMARKAR, A new polynomial-time algorithm for linear
programming, Combinatorica, Vol. 4, pp. 373-395, 1984.
[38]
L. KHACHIYAN, A polynomial algorithm in linear programming,
Sov. Math., Dokl., Vol. 20, pp. 191-194, 1979.
[39]
P. KLEINSCHMIDT AND S. ONN, Signable posets and partitionable
simplicial complexes., Discrete Comput. Geom., Vol. 15, No. 4,
pp. 443-466, 1996.
[40]
N. LINIAL, Hard enumeration problems in geometry and
combinatorics, SIAM J. Alg. Disc. Math., Vol. 7, No. 2, pp. 331-335, 1986.
[41]
E. M. LUKS, Isomorphism of graphs of bounded valence can be
tested in polynomial time, J. Comput. Syst. Sci., Vol. 25, pp. 42-65, 1982.
[42]
J. MATOUSEK, M. SHARIR, AND E. WELZL, A subexponential bound
for linear programming, Algorithmica, Vol. 16, No. 4-5, pp. 498-516, 1996.
[43]
P. MCMULLEN, The maximum numbers of faces of a convex polytope,
Mathematika, Vol. 17, pp. 179-184, 1970.
[44]
N. MEGIDDO, Linear programming in linear time when the dimension
is fixed, J. Assoc. Comput. Mach., Vol. 31, pp. 114-127, 1984.
[45]
K. MEHLHORN AND P. MUTZEL, On the embedding phase of the
Hopcroft and Tarjan planarity testing algorithm, Algorithmica, Vol. 16,
No. 2, pp. 233-242, 1996.
[46]
H. MINKOWSKI, Geometrie der Zahlen (Geometry of numbers).
Teubner Verlag, Leipzig, 1886 and 1910; reprinted by Chelsea, New
York, 1953, and by Johnson, New York, 1968.
(German).
[47]
N. E. MNËV, The universality theorems on the classification
problem of configuration varieties and convex polytopes varieties, in
Topology and Geometry - Rohlin Seminar, O. Y. Viro, ed., No. 1346 in Lecture
Notes in Mathematics, Springer-Verlag, 1988, pp. 527-543.
[48]
J. R. MUNKRES, Elements of Algebraic Topology, Addison-Wesley,
Menlo Park CA, 1984.
[49]
K. G. MURTY, A fundamental problem in linear inequalities with
applications to the travelling salesman problem, Math. Program., Vol. 2,
pp. 296-308, 1972.
[50]
S. D. NOBLE, Recognising a partitionable simplicial complex is
in NP, Discrete Math., Vol. 152, pp. 303-305, 1996.
[51]
A. PACKER, NP-hardness of largest contained and smallest
containing simplices for V- and H-polytopes, Discrete Comput. Geom.,
Vol. 28, pp. 349-377, 2002.
[52]
C. H. PAPADIMITRIOU AND M. YANNAKAKIS, On recognizing integer
polyhedra, Combinatorica, Vol. 10, No. 1, pp. 107-109, 1990.
[53]
M. E. PFETSCH, The Maximum Feasible Subsystem Problem and
Vertex-Facet Incidences of Polyhedra, PhD thesis, TU Berlin, 2002.
[54]
J. S. PROVAN, Efficient enumeration of the vertices of polyhedra
associated with network LP's, Math. Program., Vol. 63, pp. 47-64, 1994.
[55]
J. RICHTER-GEBERT, Realization Spaces of Polytopes, No. 1643 in
Lecture Notes in Mathematics, Springer-Verlag, 1996.
[56]
G.-C. ROTA, On the foundations of combinatorial theory - I.
Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie, Vol. 2,
pp. 340-368, 1964.
[57]
A. SCHRIJVER, Theory of linear and integer programming,
Wiley-Interscience, 1986.
[58]
R. SEIDEL, Constructing higher-dimensional convex hulls at
logarithmic cost per face, in Proc. 18th Ann. ACM Sympos. Theory Comput.,
pp. 404-413, 1986.
[59]
————, Convex hull computations, in Handbook of
Discrete and Computational Geometry, J. Goodman and J. O'Rouke, eds., CRC
Press, Boca Raton, 1997, ch. 19.
[60]
R. P. STANLEY, Balanced Cohen-Macaulay complexes, Trans.
Am. Math. Soc., Vol. 249, pp. 139-157, 1979.
[61]
E. STEINITZ AND H. RADEMACHER, Vorlesungen über die
Theorie der Polyeder, Springer Verlag, 1934.
Reprint 1976.
[62]
G. F. SWART, Finding the convex hull facet by facet, J.
Algorithms, Vol. 6, pp. 17-48, 1985.
[63]
T. SZABÓ AND E. WELZL, Unique sink orientations of cubes,
tech. report, ETH Zürich, 2001.
To appear in: Proc. 42nd Ann. Sympos. Found. Computer Science, Las
Vegas, Oct 14-17, 2001.
[64]
W. T. TUTTE, How to draw a graph, Proc. Lond. Math. Soc., III.
Ser., Vol. 13, pp. 743-768, 1963.
[65]
H. WEYL, Elementare Theorie der konvexen Polyeder, Comment.
Math. Helv., Vol. 7, pp. 290-306, 1935.
[66]
G. M. ZIEGLER, Lectures on Polytopes, Springer-Verlag, 1995.
Revised edition 1998.
