Regularity of vertices of polyhedra in $\mathbb{R}^2$

46 Views Asked by At

Let $P=\{x\in\mathbb{R}^n\colon (a_i)^tx\leq b_i, i=1,\dots,m\}$ be an irredundant representation of a polyhedron $P$. I want to show that if $n=2$ every vertex of $P$ is regular, that is, the set of active constraints of the vertex $\{x\}$, $\mathcal{A}(\{x\})$, suffices $|\mathcal{A}(x)|=n$.

I have no idea on how to do this, and I am not even able to think of a counterexample in higher dimensions...

1

There are 1 best solutions below

1
On

Two edges go out from every vertex in a 2D polyhedron. These two edges correspond to the active constraints...

And a pyramid over a square can be your counterexample in 3D.