Vertices of a polytope in $\mathbb R^n$ defined by $-a_i\leq x_i\leq a_i$ and $-b_{ij}\leq x_i-x_j\leq b_{ij}$ for certain positive $a_i$ and $b_{ij}$

Question

I am considering the polytope $P$ in $\mathbb{R}^n$ given by the following linear inequalities:

$$-a_i \leq x_i \leq a_i$$ $$-b_{ij}\leq x_i - x_j \leq b_{ij}$$ for all $1\leq i<j\leq n$ and certain positive numbers $a_i$ and $b_{ij}$. Is there a way to find its vertices? If not in general, maybe in the case when all $a_i$ and $b_{ij}$ are the same?

Answer 1

Here is the shape of this polytope in the 3D case when $a_i=b_{ij}=1$. Proof below.

It can be considered as the volume swept by the standard cube $(C)=[0,1]^3$ with translation vector $-\vec{AB}$ where $A(0,0,0)$ and $B=(1,1,1)$.

The red points have been obtained by a random generation of points in $(x,y,z) \in [-1,1]^3$ keeping only those such that $|y-x|\leq 1$ and $|z-x|\leq 1$ and $|z-y|\leq 1$.

This picture will look familiar if one has already "seen" 3D projections of a 4D hypercube (the fourth dimension direction being represented by the magenta colored edges). See for example paragraph ''construction'' in https://www.wikiwand.com/simple/Hypercube.

This polytope has $2 \times 7=14$ vertices :

$(1,0,0),(1,0,1),(1,1,0),(1,1,1),(0,0,1),(0,1,0),(0,1,1)$ (little blue circles) and their opposites.

Remark : please note that $(0,0,0)$ is the center of the polytope.

Sketch of proof : Why is this polytope the good one?

The first family of constraints is clearly verified. Let us concentrate on the second family. They are connected with the ''oblique'' planes. Indeed, consider for example the "oblique" plane defined by $P,Q,R$. Its equation is

$$\begin{vmatrix}1&1&0&x\\0&1&-1&y\\0&0&-1&z\\1&1&1&1\end{vmatrix}=0 \ \ \iff \ \ x-z=1$$

We find back here one of the six limits induced by the second type constraints. The five other oblique planes can be shown to be in correspondence with the five other limit cases.

Working with equal signs allows to assess the limit cases ; now, the inequalities themselves will be an immediate consequence of the limit cases : it suffices to consider them as (another) "sweeping process" :

For example, the family of parallel planes with equations $x-z=t$ for $-1 \leq t \leq 1$ realize continuous sweeping from the face defined by $x-z=1$ to the (parallel) opposite face defined by $x-z=-1$. Particular case $t=0$ gives a vectorial plane (passing through the origin).

Regarding the nD case, the solution is a straightforward generalization of the 3D case : a $(n-1)$ dimensional hypercube sliding along the (maximal length) diagonal joining point $A=(0,0,...0)$ to point $B=(1,1,...1)$, the sliding direction being given again by $-\vec{AB}$.

Remark : this polytope is the Minkowski sum of the 3D (resp. nD) cube (resp hypercube) with segment line $AB$ as defined just above.

Another remark : Have a look at the answer given below by @user964213 (M. J. DE LA PUENTE) dealing with so-called "alcoved polytopes" in the framework of tropical geometry.

Answer 2

I have studied these polytopes for years (alone and together with P.L. Clavería). S. Sergeev have also studied some aspects of them.

I call theses polytopes alcoved polytopes (other authors use the term alcoved in more generality). The process to obtain a d-alcoved polytope from a d-box (i.e., a d-orthotope) is to cant, i.e., to bevel some (d-2)-faces (but not all) of the d-box. Only the (d-2)-faces meeting two special points of the d-box may (but not necesarily have to) be canted. The two special points in the d-box are: the maximal point (coordinatewise) called North pole and the minimal point (coordinatewise) called South pole.

Each canted (d-2)-face is done so by a positive ammount (and canting by zero is the same as not-canting). If all these ammounts are positive and equal, we say that the alcoved is isocanted. An isocanted alcoved polytope is maximal in number of facets but not maximal in number of vertices.

You can find lots of proved properties in the following references. Some proofs use notions of tropical algebra. The three more relevant ones are:

M. J. DE LA PUENTE. Quasi-Euclidean classification of alcoved convex polyhedra. Linear and Multilinear Algebra. 10, (2019) pp. 2110 - 2142.

M. J. DE LA PUENTE and P.L. CLAVERÍA. Isocanted alcoved polytopes. Applications of Mathematics. 6, pp. 703 -736. (2020)

M. J. DE LA PUENTE and P.L. CLAVERÍA. Volume of Alcoved Polyhedra and Mahler Conjecture, DOI 10.1145/3208976.3208990. ISSAC 2018. ISBN 978-1-4503-5550-6