Consider a set $C$ of vectors of integers $x\in\mathbb N^d$ satisfying
$$ \begin{align} \forall\ i=1..d & \ \ [0 \leq \ell_i \leq x_i \leq u_i]\\ \forall\ i=1..d-1 & \ \ [x_{i+1} \leq x_i] \end{align} $$
where $\ell_i, u_i,\ i=1..d$ are bounds satisfying $\forall i=1..d-1\ [\ell_{i+1} \leq \ell_{i}]$ so that the set is nonempty. This is a convex polytope (ignoring the $\in\mathbb N^d$ part), and I'm interested in finding its vertices.
My current approach is:
- Enumerate all integer vectors/points in the "hyperrectangle" from the first condition
- Drop all points not satisfying the second condition
- Pass the set of points to a convex-hull finder
But I suspect there is as more straightforward way to find these vertices, given the simple structure of the problem.
It seems the following.
Let $x=(x_1,\dots,x_d)\in C$. We shall call an index $i$ fixed provided $x_i=\ell_i$ or $x_i=u_i$.
Proposition. A vector $x=(x_1,\dots,x_d)\in C$ is a vertex of $C$ iff for each index $i$ there exists a fixed index $j$ such that $x_i=x_j$.
Proof. First of all we remark that a point $x$ is a vertex of $C$ iff there exist no different points $y,z\in C$ and a number $0<\lambda<1$ such that $x=\lambda y+(1-\lambda) z.$
Necessity. Suppose that there exists an index $i$ such that there exists no fixed index $j$ such that $x_i=x_j$. Let $j_1$ be a largest fixed index smaller than $i$, or $0$ is there is no such index. Let $j_2$ be a smallest fixed index larger than $i$, or $d+1$ is there is no such index. Define points $y,z\in\Bbb N$ as follows. For each $j$ put $y_j=x_j-1$ and $z_j=x_j-1$, if $j_1<j<j_2$, and put $y_j=z_j=x_j$, otherwise. It is easy to check that $y,z\in C$ and $x=(y+z)/2$, so $x$ is not a vertex of $C$.
Sufficiency. Suppose that $x$ is not a vertex of $C$. Then there exist points $y,z\in C$ and a number $0<\lambda<1$ such that $x=\lambda y+(1-\lambda) z.$ Since $y\ne z,$ there exists an index $i$ such that $y_i\ne z_i$. Suppose that there exists a fixed index $j$ such that $x_i=x_j$. Since the index $j$ is fixed, $y_j=z_j=x_j=x_i$. Suppose that $j\le i$. Since $y,z\in C$, $y_i\le y_j$ and $z_i\le z_j$. Then $x_i=\lambda y_i+(1-\lambda) z_i\le x_i$. Therefore $y_i=z_i=x_i,$ a contradiction. The case $j\ge i$ is considered similarly.$\square$