# max length or size of a convex set

I want to maximize $||x-y||$ with $x$ and $y$ in $C$ where $C$ is the intersection of some discs. We assume the intersection is nonempty, and closed. I am thinking, how to formulate it as a semidefinite programmimg problem? Does anyone know how?

-
For future reference, you can edit your question. There is no need to post as a new one. –  Willie Wong Oct 3 '10 at 11:59
add comment

## 1 Answer

I hope that the word "disc" indicates that we work in 2-dimensional Euclidean space. Then an intersection of discs would be something like a polygon, just that the sides are not straight lines but arcs of a circle. It should be possible to save the intersection in some data structure. And then one can compute the maximum distance from each arc to each other arc and take the maximum value.

To compute the maximum distance between to given Arcs $A_1$ and $A_2$ let $x_i\in A_i$ be two points such that $d(x_1,x_2)=\sup\{d(x,y)|x\in A_1,y\in A_2\}$. (Existence follows from compactness). If you take a unit speed parametrization $\gamma_1,\gamma_2$ of the arcs, and times $t_i$ with $\gamma_i(t_i)=x_i$. Assuming, that $x_1$ is not the endpoint of the arc $A_1$, then the function $\mathbb{R}\rightarrow \mathbb{R} \qquad t\mapsto d(\gamma_1(t),x_2)$ obtains a maximum at $t$, so its differential must be $0$ at $t_1$. But this is just the scalar product of $\gamma'_1(t_1)$ and the gradient of $d(-,x_2)$ at $\gamma(t)$, which can be seen as the direction of the line connecting $x_1$ and $x_2$.

This should make it possible to compute the distance by looking at finitely many cases. (Both endpoints, one inner point, two inner points).

Hope I understood the question right.

-
If there are $n$ discs, how many "sides" can the intersection have? If the answer grows exponentially with $n$, your procedure - while perfectly correct - may be impractical. Also, I'm not sure I understand the assertion about computing the maximum distance between points on two given arcs (nor how "minimizing points" are relevant to a maximization problem). –  Gerry Myerson Oct 3 '10 at 22:41
I see you've edited your answer, but I still can't parse the 2nd paragraph. If you are asserting that the line that gives the greatest distance between two given arcs must be orthogonal to those arcs, well, that's certainly not true, but maybe that's not what you are saying. –  Gerry Myerson Oct 4 '10 at 12:15
You are right, the second part was really massed up. however I wanted to wait with an edit until I had an idea, how one could show, that there are only lineary many sides neccesary. –  HenrikRüping Oct 4 '10 at 12:59
add comment