# 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 guess this link shows that it is NP-Hard to event achieve a constant approximation? – amos Feb 28 at 12:12

## 1 Answer

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 & -I \\ -I & I \end{bmatrix}.$$