2
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ I guess this link shows that it is NP-Hard to event achieve a constant approximation? $\endgroup$ – amos Feb 28 at 12:12
3
$\begingroup$

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}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.