Efficient algorithm to compute the diameter of a convex set? Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set?
It is possible to do it efficiently for a set of points, but imagine that the set is described by the intersection of linear equations in high dimensional space, so the number of vertices of the set can be exponential in the number of inequalities.
Given a direction, we can easily compute the distance of furthest points along that direction using linear programming. The question is how do we find that direction?
I suspect that if the points in your set are expressed as $Ax \le b$ and you're considering the Euclidean distance, then you can solve the following quadratic program with the ellipsoid method:
$$
\max  \sum_i (x^2_i+y^2_i-2x_i y_i) \\
Ax \le b \\
Ay \le b.
$$
Where we used the fact that optimizing $|x-y|$ is the same as optimizing $ \frac{1}{2} |x-y|^2 = \frac{1}{2} \sum_i (x_i-y_i)^2 = \frac{1}{2} \sum_i (x_i^2+y_i^2 - 2x_iy_i)$.
The objective function can also be written as $\frac{1}{2} z^T Q z$, where $z=(x,y)$ and:
$$
Q= \begin{bmatrix}
I &amp; -I \\
-I &amp; I
\end{bmatrix}.
$$