H-representation and V-representation

Definition

Let $n \ge 1$ , and let $P \subseteq \R^n$ be a convex polytope.

A V-representation of $P$ is a finite set $V \subseteq \R^n$ with $P = \mathrm{conv}(V)$ , the convex hull of $V$ .
An H-representation of $P$ is a pair $(A, b)$ of a real $m \times n$ matrix $A$ and a vector $b \in \R^m$ with $P = \set{x \in \R^n : A x \le b}$ . Here $\le$ is taken coordinatewise.

Equivalently, an H-representation is a finite family of closed half-spaces whose intersection is $P$ .

Remarks

Example: for $P = [0, 1]^2$ , the set $V = \set{(0, 0), (1, 0), (0, 1), (1, 1)}$ is a V-representation, and the inequalities $-x_1 \le 0$ , $x_1 \le 1$ , $-x_2 \le 0$ , $x_2 \le 1$ form an H-representation. Non-example: the inequalities $-x_1 \le 0$ , $-x_2 \le 0$ alone are not an H-representation of $[0, 1]^2$ ; they define the unbounded quadrant, which contains $(2, 0) \notin P$ . Representations are not unique, since points and inequalities can be added without changing $P$ . The smallest V-representation is the set of vertices of $P$ , and for a full-dimensional $P$ an irredundant H-representation has exactly one inequality for each facet, unique up to positive scaling. Every convex polytope has both kinds of representation; this is the Minkowski–Weyl theorem.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Convex hull concept
Convex polytope concept
H-representation and V-representation definition

Tag	`KNP5ZEQ458`
URI	`m2://KNP5ZEQ458`
Kind	definition
Writing	W0 stub
MSC	52B11, 52B55, 90C05
Defines	H-representation and V-representation
Uses	Convex polytope, Convex hull

H-representation and V-representation

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here