Go up to Main PageGo forward to 2 Coordinate Descriptions |
XHTML 1.0 |

Convex polyhedra, i.e., the intersections of finitely many closed
affine half-spaces in * R^{d}*, are important objects in various areas
of mathematics and other disciplines. In particular, the compact ones
among them (

Probably the most important reason for the tremendous growth of
interest in the theory of convex polyhedra in the second half of the
*20 ^{th}* century was the fact that

Since the interest in the theory of convex polyhedra to a large extent
comes from algorithmic problems, it is not surprising that many
algorithmic questions on polyhedra arose in the past. But also
inherently, convex polyhedra (in particular: polytopes) give rise to
algorithmic questions, because they can be treated as finite objects
by definition. This makes it possible to investigate (the smaller ones
among) them by computer programs (like the `polymake`-system
written by Gawrilow and Joswig, see [25] and
[26][27]). Once chosen to exploit this possibility, one
immediately finds oneself confronted with many algorithmic challenges.

This paper contains descriptions of 35 algorithmic problems about polyhedra. The goal is to collect for each problem the current knowledge about its computational complexity. Consequently, our treatment is focused on theoretical rather than on practical subjects. We would, however, like to mention that for many of the problems computer codes are available.

Our choice of problems to be included is definitely influenced by personal interest. We have not spent particular efforts to demonstrate for each problem why we consider it to be relevant. It may well be that the reader finds other problems at least as interesting as the ones we discuss. We would be very interested to learn about such problems. The collection of problem descriptions presented in this paper is intended to be maintained as a (hopefully growing) list at this site.

Almost all of the problems are questions about polytopes. In some cases the corresponding questions on general polyhedra are interesting as well. It can be tested in polynomial time whether a polyhedron specified by linear inequalities is bounded or not. This can be done by applying Gaussian elimination and solving one linear program.

Roughly, the problems can be divided into two types: problems for
which the input are "geometrical" data and problems for which the
input is "combinatorial" (see below). Actually, it turned out that
it was rather convenient to group the problems we have selected into
the five categories "Coordinate Descriptions"
(Sect. 2), "Combinatorial Structure"
(Sect. 3), "Isomorphism"
(Sect. 4), "Optimization"
(Sect. 5), and "Realizability"
(Sect. 6). Since the boundary complex of a
simplicial polytope is a simplicial complex, studying polytopes leads
to questions that are concerned with more general (polyhedral)
structures: *simplicial complexes*. Therefore, we have added a
category "Beyond Polytopes" (Sect. 7), where a few
problems concerned with general (abstract) simplicial complexes are
collected that are closely related to similar problems on polytopes.
We do not consider other related areas like oriented matroids.

The problem descriptions proceed along the following scheme. First
input and output are specified. Then a summary of the knowledge on the
theoretical complexity is given, e.g., it is stated that the
complexity is unknown ("Open") or that the problem is *NP*-hard.
This is done for the case where the dimension (usually of the input
polytope) is part of the input as well as for the case of fixed
dimension; often the (knowledge on the) complexity status differs for
the two versions. After that, comments on the problems are given
together with references. For each problem we tried to report on the
current state of knowledge according to the literature. Unless stated
otherwise, all results mentioned without citations are either
considered to be "folklore" or "easy to prove." At the end
related problems in this paper are listed.

For all notions in the theory of polytopes that we use without
explanation we refer to Ziegler's book [66]. Similarly, for
the concepts from the theory of computational complexity that play a
role here we refer to Garey and Johnson's classical
text [23]. Whenever we talk about *polynomial
reductions* this refers to polynomial time Turing-reductions. For
some of the problems the output can be exponentially large in the
input. For these problems the interesting question is whether there
is a *polynomial total time* algorithm, i.e., an algorithm whose
running time can be bounded by a polynomial in the sizes of the input
and the output (in contrast to a *polynomial time* algorithm
whose running time would be bounded by a polynomial just in the input
size). Note that the notion of "polynomial total time" only makes
sense with respect to problems which explicitly require the output to
be non-redundant.

A very fundamental result in the theory of convex polyhedra is due to
Minkowski [46] and Weyl [65]. For the special case of
polytopes (to which we restrict our attention from now on) it can be
formulated as follows. Every polytope *P⊂ R^{d}* can be specified
by an

One of the basic properties of a polytope is its dimension. If the
polytope is given by a *V*-description, then it can easily
be determined by Gaussian elimination (which, carefully done, is a
cubic algorithm; see, e.g., [57]). If the polyhedron is
specified by an *H*-description, computing its dimension can
be done by linear programming (actually, this is polynomial time
equivalent to linear programming).

Furthermore, some of the problems may also be interesting in their
polar formulations, i.e., with "the roles of *H*- and
*V*-descriptions exchanged." Switching to the polar
requires to have a relative interior point at hand, which is easy to
obtain if a *V*-description is available, while it needs
linear programming if only an *H*-description is specified.

We will especially be concerned with the combinatorial types of
polytopes, i.e., with their *face lattices* (the sets of faces,
ordered by inclusion). In particular, some problems will deal with the
* k-skeleton* of a polytope, which is the set of its faces of
dimensions less than or equal to

A third important combinatorial structure associated with a
polytope *P* is its (abstract) graph *G _{P}*, i.e., any graph that
is isomorphic to the graph having the vertices of

Throughout the paper, *n* refers to the number of vertices or points
in the given *V*-description, respectively, depending on the
context. Moreover, *m* refers to the number of facets or inequalities
in the given *H*-description, respectively, and *d* refers
to the dimension of the polytope or the ambient space,
respectively.

Why are some symbols not displayed correctly? |