Some algorithmic problems in polytope theory. (English) Zbl 1027.65032

Kaibel, Volker; Pfetsch, Marc E.

Joswig, Michael (ed.) et al., Algebra, geometry, and software systems. Berlin: Springer. 23-48 (2003).

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

Reviewer: Corina Mohorianu (Iaşi)

MSC:

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

Keywords:

polyhedra; polytopes; Euler characteristic; simplicial complexes; homology; combinatorical structure; graphs; face lattices; affine equivalence; computational complexity

Software:

polymake