0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ For future reference, you can edit your question. There is no need to post as a new one. $\endgroup$ Oct 3, 2010 at 11:59

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$ Oct 3, 2010 at 22:41
  • $\begingroup$ 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. $\endgroup$ Oct 4, 2010 at 12:15
  • $\begingroup$ 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. $\endgroup$ Oct 4, 2010 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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