Polyhedral sets

Fri, Jan 15, 2016 01:00 CET

Tags: Geometry, Definitions

A polyhedral set in \(\mathbb{R}^d\) is the intersection of a finite number of closed halfspaces, and a (convex) polytope is a bounded polyhedral set. This definition of a polytope is called a halfspace representation (H-representation or H-description).

A defining halfspace of a polyhedral set \(P\) is a facet-defining halfspace for \(P\).

A \(k\)-face of a polyhedral set \(P\) is the intersection of \(P\) with \(d-k\) (non-redundant) hyperplanes defining \(P\). Vertices, edges, and facets are \(0\)-, \(1\)-, and \((d-1)\)-faces.

There exist infinitely many H-descriptions of a convex polytope. However, for a full-dimensional convex polytope, the minimal H-description is in fact unique and is given by the set of the facet-defining halfspaces.

The set of extreme points (vertices) of a polyhedral set \(P\) will be denoted \(\mathop{ext} P\).

The set of extreme rays of \(P\), \(\mathop{extr} P\), is the set of rays \(e\) emanating from the origin \(0\) such that there is some point \(q \in P\) for which \((q+e)\) is an edge of \(P\) (here ‘+’ between pointsets means pointwise sum).

A \(k\)-simplex \(S\) is a \(k\)-dimensional polytope with \(|\mathop{ext} S| = k+1\).

A nonzero element \(x\) of a polyhedral cone \(C \subseteq \mathbb{R}^n\) is called an extreme ray if there are \(n − 1\) linearly independent constraints binding at \(x\).

An extreme ray of the recession cone associated with a polyhedral set \(P\) is also called an extreme ray of \(P\).

TO BE CONTINUED …