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.

  • 1 Introduction
  • 2 Coordinate Descriptions
  • 3 Combinatorial Structure
  • 4 Isomorphism
  • 5 Optimization
  • 6 Realizability
  • 7 Beyond Polytopes
  • References

  •   This document uses the Symbol-font for typesetting mathematical symbols. The Microsoft Explorer uses this font by default. If these symbols are not displayed correctly and you use Netscape on a UNIX operating system this can be fixed as described here.

    Updated: 10/10/2003 Generated from LaTeX by Hyperlatex