Some Algorithmic Problems

in Polytope Theory

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 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 | Generated from LaTeX by Hyperlatex |