Question

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?

Answer 1

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.