backup forward

Go backward to 9 Recognizing Integer Polyhedra
Go up to 2 Coordinate Descriptions
Go forward to 11 Minimum Triangulation
XHTML 1.0

10 Diameter

Input: Polytope P in H-description
Output: The diameter of P
Status (general): NP -hard
Status (fixed dim.): Polynomial time
Frieze and Teng [21] gave the proof of NP-hardness. For fixed dimension, one can enumerate all vertices (Problem 1), construct the graph and then compute the diameter in polynomial time.

The complexity status is unknown for simple polytopes. For simplicial polytopes the problem can be solved in polynomial time: Since simplicial polytopes have at most as many vertices as facets, one can enumerate their vertices (see Problem 1), and finally compute the graph (and hence the diameter) from the vertex-facet incidences in polynomial time.

If P is given in V-description, one can compute the graph (1-skeleton, see Problem 5) and hence the diameter in polynomial time.


backup forward Why are some symbols not displayed correctly?