×

zbMATH — the first resource for mathematics

Constructions and complexity of secondary polytopes. (English) Zbl 0714.52004
The paper presents a self-contained and comprehensive study of secondary polytopes. The secondary polytope \(\Sigma\) (\({\mathcal A})\) of a configuration \({\mathcal A}\) of n points in affine (d-1)-space is an (n-d)- polytope whose vertices correspond to regular triangulations of conv(\({\mathcal A}).\)
Besides the original Gelfand-Kapranov-Zelevinsky construction a construction of \(\Sigma\) (\({\mathcal A})\) as the projection of a universal polytope \({\mathcal U}({\mathcal A})\) is given.
Especially interesting is a third construction of \(\Sigma\) (\({\mathcal A})\) using Gale transforms. This point of view is the most constructive one. It leads to an algorithm for computing all regular triangulations of \({\mathcal A}\). The rest of the paper deals with other aspects of the computational complexity of secondary polytopes (for instance a bound for the number of faces of \(\Sigma\) (A) is given).
Reviewer: H.-D.Hecker

MSC:
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
52B55 Computational aspects related to convexity
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52B35 Gale and other diagrams
68Q25 Analysis of algorithms and problem complexity
05B30 Other designs, configurations
PDF BibTeX Cite
Full Text: DOI
References:
[1] Bayer, M.; Sturmfels, B., Lawrence polytopes, Canad. J. math., XLII, 62-79, (1990) · Zbl 0743.05010
[2] Billera, L.J.; Munson, B.S., Triangulations of oriented matroids and convex polytopes, SIAM J. algebraic discrete methods, 5, 515-525, (1984) · Zbl 0557.05026
[3] {\scA. Björner, M. LasVergnas, B. Sturmfels, N. White, and G. Ziegler}, “Oriented Matroids,” Cambridge Univ. Press, to appear.
[4] Buck, R.C., Partition of space, Amer. math. monthly, 50, 541-544, (1943) · Zbl 0061.30609
[5] Danilov, V.I., The geometry of toric varieties, Russian math. surveys, Uspekhi mat. nauk., 33, 85-134, (1978), translated from · Zbl 0425.14013
[6] Edelsbrunner, H., Algorithms in combinatorial geometry, (1987), Springer-Verlag Berlin/New York · Zbl 0634.52001
[7] Edelsbrunner, H.; O’Rourke, J.; Seidel, R., Constructing arrangements of lines and hyperplanes with applications, SIAM J. comput., 15, 341-363, (1986) · Zbl 0603.68104
[8] Federer, H., Geometric measure theory, (1969), Springer-Verlag Berlin/New York · Zbl 0176.00801
[9] Filliman, P., Exterior algebra and projections of polytopes, Discrete comput. geom., 5, 305-322, (1990) · Zbl 0698.15012
[10] Gel’fand, I.M.; Kapranov, M.M.; Zelevinsky, A.V., Newton polyhedra of principal \(A\)-determinants, Soviet math. dokl., 308, 20-23, (1989) · Zbl 0742.14042
[11] Gel’fand, I.M.; Kapranov, M.M.; Zelevinsky, A.V., Discriminants for polynomials in several variables and triangulations of Newton polytopes, (1989), [In Russian]
[12] Gritzmann, P.; Sturmfels, B., Minkowski addition of polytopes: computational complexity and applications to Gröbner bases, (1990), manuscript
[13] Grünbaum, B., Convex polytopes, (1967), Interscience London · Zbl 0163.16603
[14] {\scM. Haiman}, Constructing the associahedron, unpublished manuscript.
[15] Lee, C., Some notes on triangulating polytopes, (), 173-181
[16] Lee, C., The associahedron and triangulations of the n-gon, European J. combin., 10, 551-560, (1989) · Zbl 0682.52004
[17] {\scC. Lee}, Regular triangulations of polytopes, in “Applied Geometry and Discrete Mathematics”, DIMACS Series, Amer. Math. Soc., to appear.
[18] McMullen, P., Transforms, diagrams and representations, () · Zbl 0445.52006
[19] Oda, T., Convex bodies and algebraic geometry, an introduction to the theory of toric varieties, (1985), Springer-Verlag Berlin/New York
[20] Pachner, U., PL-homeomorphic manifolds are equivalent by elementary shellings, (1989), Universität Bochum, Preprint 126
[21] Sleator, D.D.; Tarjan, R.E.; Thurston, W.P., Rotation distance, triangulations, and hyperbolic geometry, J. amer. math. soc., 1, 647-681, (1988) · Zbl 0653.51017
[22] Smilansky, Z., Decomposability of polytopes and polyhedra, Geom. dedicata, 24, 29-49, (1987) · Zbl 0632.52006
[23] Stasheff, J., Homotopy associativity of H-spaces, I, Trans. amer. math. soc., 108, 275-292, (1963) · Zbl 0114.39402
[24] Sturmfels, B., Zur linearen realisierbarkeit orientierter matroide, (1985), Technische Hochschule Darmstadt Diplomarbeit
[25] Sturmfels, B., Some applications of affine gale diagrams to polytopes with few vertices, SIAM J. discrete math., 1, 121-133, (1988) · Zbl 0728.52010
[26] Sturmfels, B., Neighborly polytopes and oriented matroids, European J. combin., 9, 537-546, (1988) · Zbl 0693.05019
[27] Zaslavsky, T., Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, () · Zbl 0296.50010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.