polytope

In n dimensional euclidian space Rⁿ, a polytope is a compact set delimited by a finite number of hyperplanes.

In other words, it's the n dimensional generalisation of a polygon (in R²) and a polyhedron (in R³). Some authorities prefer to modify the definition above not to allow "holes" in the polytope (in more dimensions, holes become even more complicated than in 3 dimensions!).

Many amazing properties of polytopes, especially convex ones, are known. For instance, linear programming occurs on a polytope (assuming all variables may be bounded); the analysis of complexity for algorithms to solve linear programming involves combinatorial properties of polytopes.

(a) The convex hull of a finite point set.

(b) The intersection of a finite collection of halfspaces.

These two definitions differ in that polytopes of type (a) are always bounded.

--back to combinatorics--