Some algorithmic problems in polytope theory

MaRDI QIDQ4418120zbMATH OpenFDO

Authors Volker Kaibel, Marc Emanuel Pfetsch

Publication date 7 August 2003

Full work available at URL https://arxiv.org/abs/math/0202204

zbMATH Keywords

affine equivalencecombinatorical structurecomputational complexityEuler characteristicface latticesgraphshomologypolyhedrapolytopessimplicial complexes

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)

Review text

This paper contains descriptions of 35 algorithmic problems about polyhedra, the goal being to study for each problem its computational complexity. For many of the problems computer codes are available. The authors especially are concerned with the combinatorial types of polytopes (their face lattices, the vertex-facet incidences of a \(d\)-polytope, their graphs). For the entire collection see [Zbl 1008.00013].

Recommendations

• scientific article; zbMATH DE number 3876926
• On the complexity of polytope isomorphism problems
• Combinatorial face enumeration in convex polytopes
• polymake: a framework for analyzing convex polytopes
• The Complexity of Vertex Enumeration Methods

Cited in

(32)

• Some algorithmic problems for projective planes
• Polymatroids: Construction and random algorithms
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• An orderly algorithm and some applications in finite geometry
• Complexity and algorithms for Euler characteristic of simplicial complexes
• Shellings from relative shellings, with an application to NP-completeness
• Recognizing Cartesian products of matrices and polytopes
• Which nonnegative matrices are slack matrices?
• Problems on polytopes, their groups, and realizations
• Convex hulls, oracles, and homology
• Partitioning the projective plane and the dunce hat
• Reachability of weakly nonlinear systems using Carleman linearization
• An algorithm for enumeration of polyhedra and orbifolds
• Sum of squares certificates for containment of \(\mathcal{H}\)-polytopes in \(\mathcal{V}\)-polytopes
• Algorithms for the frame of a finitely generated unbounded polyhedron
• scientific article; zbMATH DE number 3876926 (Why is no real title available?)
• Topologically consistent algorithms related to convex polyhedra
• Reconstructing a simple polytope from its graph
• scientific article; zbMATH DE number 761902 (Why is no real title available?)
• scientific article; zbMATH DE number 911850 (Why is no real title available?)
• scientific article; zbMATH DE number 1393410 (Why is no real title available?)
• Shellability is NP-complete
• Obstructions to shellability, partitionability, and sequential Cohen-Macaulayness
• iB4e: a software framework for parametrizing specialized LP problems
• Eigenpolytope Universality and Graphical Designs
• Slack matrices, k-products, and 2-level polytopes
• Recognition of Seifert fibered spaces with boundary is in NP
• Complexity of simplicial homology and independence complexes of chordal graphs
• Hardness of finding combinatorial shortest paths on graph associahedra
• Construction theorems for polytopes
• Algorithmic complexity of a problem of idempotent convex geometry.
• Mixed-up trees: the structure of phylogenetic mixtures

Describes a project that uses

Uses Software

• polymake

This page was built for publication: Some algorithmic problems in polytope theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4418120)