Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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