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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I guess this link shows that it is NP-Hard to event achieve a constant approximation? $\endgroup$ Commented Feb 28, 2021 at 12:12

1 Answer 1

Reset to default
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}. $$

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.