$\newcommand{\R}{\mathbb{R}}$
The diameter of a convex polytope is the maximum distance between any pair of vertices.
Contents:
Let $P$ be a polytope in a $n$-dimensional ambient space. If we have access to the V-representation of the polytope, then we can proceed as follows:
1. diam = 0; vlist = P.vertices_list()
2. for j = 1, ..., n:
for k = j+1, ..., n:
diam = max(diam, norm(vlist[j], vlist[k]))
3. output diam
The time complexity of this algorithm is $O(n^2)$.
By default, the function diameter_vertex_enumeration works in the supremum norm. For example:
In [1]:
from polyhedron_tools.misc import diameter_vertex_enumeration
diameter_vertex_enumeration(polytopes.hypercube(3))
Out[1]:
A second argument can be passed to specify the norm.
In [2]:
diameter_vertex_enumeration(polytopes.hypercube(3), p=2)
Out[2]:
In fact for the $n$-hypercube, the diameter is $2\sqrt{n}$. In practice, the computation for high dimensions could take a very long time because the vertices may increase exponentially. For instance, the $n$-dimensional hypercube has $2^n$ vertices.
In [3]:
diameter_vertex_enumeration(polytopes.hypercube(6), p=2)
Out[3]:
An alternative approach is to use the $H$-representation of the polytope.
Below we describe an algorithm that is inspired from Inner and outer approximations of polytopes using boxes; see that paper and references therein for further details on this or related enclosing problems.
If $l, u \in \R^n$, with $l_i \leq u_i$ for all $i = 1,\ldots,n$, consider the hyperrectangle $\mathcal{B}(l, u)$, defined as the product of intervals $$ \mathcal{B}(l, u) = [l_1,u_1]\times [l_2, u_2]\times \cdots \times [l_n, u_n]. $$
Let $P$ be a given polytope in ambient dimension $n$ and defined by $m$ constraints. Consider the following algorithm to compute the diameter of $P$ in the supremum norm:
1. For j = 1, ..., n:
(i) l_j := min x_j such that x in P
(ii) u_j := max x_j such that x in P
2. Output max_j (u_j - l_j)
The time complexity of this algorithm is $O(n \times LP(m, n))$.
Using inner products, $x_j = \langle x, e_j \rangle$ for each $j$, where $e_j$ is the $j$-element of the canonical basis of $\R^n$. If $\rho_P(d)$ denotes the support function of $P$ evaluated at $d \in \R^n$, we can pose the problem:
max x_j such that x in P as evaluating $\rho_P(e_j)$, and similarlymin x_j such that x in P as evaluating $-\rho_P(-e_j)$.Example:
In [2]:
from polyhedron_tools.misc import diameter_support_function, polyhedron_to_Hrep
[A, b] = polyhedron_to_Hrep(7*polytopes.hypercube(5))
diam, u, l = diameter_support_function(A, b)
diam, u, l
Out[2]: