Vertex of a polytope

Builds on Convex polytope Face of a convex set Extreme point Convex hull

Definition

Let $P \subset \R^d$ be a convex polytope. A vertex of $P$ is a face of $P$ of dimension $0$ , identified with the single point it contains. Equivalently, a point $v \in P$ is a vertex if there is a vector $c \in \R^d$ such that $c \cdot v > c \cdot x$ for every $x \in P$ with $x \ne v$ .

Remarks

Example: in the square $P = [0,1]^2$ , the point $v = (1,1)$ is a vertex. Take $c = (1,1)$ : then $c \cdot v = 2$ , and $c \cdot x = x_1 + x_2 < 2$ for every other point $x$ of $P$ .

Non-example: the point $(1, \tfrac12)$ of the same square is not a vertex. For any $c$ , the points $(1, \tfrac12 \pm t)$ for small $t > 0$ lie in $P$ , and $c \cdot x$ is at least $c \cdot (1,\tfrac12)$ at one of them, so no $c$ singles it out.

The vertices of $P$ are exactly its extreme points. If $V$ is the set of vertices, then $P$ is the convex hull of $V$ , and every finite set whose convex hull is $P$ contains $V$ .

Reading path

To understand this page from the ground up, read these 5 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

Tag	`BETJYRCRJB`
URI	`m2://BETJYRCRJB`
Kind	definition
Writing	W0 stub
MSC	52B05, 52B11
Defines	Vertex of a polytope
Uses	Convex polytope, Face of a convex set, Extreme point, Convex hull

Vertex of a polytope

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here