Some Algorithmic Problems
in Polytope Theory


Volker Kaibel and Marc E. Pfetsch

first released: 2/22/2002  -   last updated: 3/20/2003   -   Changes

These web pages collect algorithmic questions about combinatorial and geometric properties of convex polytopes.

We give a list of 35 problems; for each the current state of knowledege on its theoretical complexity status is reported. The problems are grouped into the sections listed below.

A printed version of this list appears in the book

"Algebra, Geometry, and Software Systems"
Editors: Michael Joswig and Nobuki Takayama
Springer-Verlag, 2003

The collection is being updated at this site. We would be very interested if you have ideas for further problems or comments on this list.

This document is written in XHTML 1.0. Some parts of this document might not be displayed correctly unless you use a "new" browser (e.g. the "Internet Explorer" from version 5 on or "Netscape" (Mozilla) from version 6 on). For instance, the symbols used to typeset mathematics in this document cannot be displayed by older versions. Furthermore, problems with the style sheets can occur.

If you have a browser that does not display the symbols correctly, you might want to try the symbol version which uses the symbol font to typeset mathematics and uses HTML 3.2. However, for most browsers you have to install this font (see the comments there).

Updated: 10/10/2003 Valid XHTML 1.0! Generated from LaTeX by Hyperlatex