# Maximum distance between two points of a polyhedron

Given a (bounded and feasible) polyhedron, $$P=\{x\mid Ax\le b\}$$ and a number $$\gamma > 0$$, decide if there are two points $$x, y \in P$$ such that $$\Vert x - y\Vert_p \ge \gamma$$.

1. Is there an $$\ell_p$$ norm for which the above problem is poly-time solvable?
2. Is there an $$\ell_p$$ norm for which the above is $$NP$$-hard?
• If yes, can the maximum distance between any two points be approximated in poly-time? ($$\max \Vert x - y\Vert_p$$ s.t. $$x, y \in P$$)
• Alternatively, can (provably) good-quality upper bounds be computed for this problem in poly-time?

The maximum distance between points in the polytope is called diameter (terminology note: ^1), or inner 1-radii (times two) [2] of the polytope $$P$$.

A closely related problem is the norm maximization problem of computing $$\max_{x \in P'} \|x\|_p$$. If $$P'$$ is centrally symmetric i.e. $$P' = -P'$$, then the diameter is twice the maximum norm. Conversely, let $$P' = P - P = \{x_1 - x_2 \mid x_1, x_2 \in P\}$$ then $$P'$$ is centrally symmetric and the maximized norm on $$P'$$ is equal to the diameter of $$P$$.

For $$p = \infty$$, the problem is polynomial-time solvable by trying all the dimensions. Solve $$\max_{x \in P} x_i$$ and $$\min_{x \in P} x_i$$ for every $$i$$ and take the maximum difference.

For every $$1 \leq p < \infty$$, maximizing the $$L^p$$-norm, and therefore computing the diameter, is NP-hard [1] [2].

For every $$2 \leq p < \infty$$, the problem doesn't have a polynomial-time constant-factor approximation algorithm unless P=NP [3].

^1: In literature, a different measure of a polytope is also simply called diameter (diameter of the unweighted graph of 1-skeleton), not to be confused.

• [1]: Bodlaender, Hans L., et al. "Computational complexity of norm-maximization." Combinatorica 10 (1990): 203-225.
• [2]: Gritzmann, Peter, and Victor Klee. "Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces." Mathematical programming 59.1 (1993): 163-213.
• [3]: Brieden. "Geometric Optimization Problems Likely Not Contained in APX." Discrete & Computational Geometry 28 (2002): 201-209.
• For $p=1$ is any approximation known? Commented Jun 5 at 17:09
• @LisaE. I couldn't find results on the p=1 approximation case. Commented Jun 5 at 17:41