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

Dear all,

let $B_\delta(p):=\{x\in\mathbb{R}^d:||x-p||_2\leq \delta\}$ be a $d$-dimensional closed ball.

Now I do not have one ball, but four: $B_{r_1}(p)$, $B_{r_2}(p)$, $B_{s_1}(q)$ and $B_{s_2}(q)$. Furthermore, the following properties hold:

  • $r_1+s_1\geq ||p-q||_2$, thus $B_{r_1}(p)\cap B_{s_1}(q)\neq \emptyset$,
  • $r_2+s_2\geq ||p-q||_2$, thus $B_{r_2}(p)\cap B_{s_2}(q)\neq \emptyset$.

Now I want to get an expression for

\[ \sup_{x\in B_{r_1}(p)\cap B_{s_1}(q)}\quad \sup_{y\in B_{r_2}(p)\cap B_{s_2}(q)} \quad ||x-y||_2. \]

I have been racking my head over it, but I do not find an elegant solution. If nothing else helps, I could only solve the problem for $d=2$ and represent the hull of the balls in parametric form and do some minimization there. But I would rather like a more general approach.

Here a small drawing of one of the scenarios that might happen: Example Drawing The distance of interest here is between the upper intersection of the two red balls ($B_{r_1}(p)$ and $B_{s_1}(p)$) and the lower intersection of the two black balls. Roughly measured, this equals 3.

Any help would be welcome. Thanks in advance.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

Let $q - p = u$ and $\|u\| = d$. Let $x = p + t_1 u + v_1 \in B_{r_1}(p) \cap B_{s_1}(q)$ and $y = p + t_2 u + v_2 \in B_{r_2}(p) \cap B_{s_2}(q)$ where $t_i \in {\mathbb R}$ and $v_i \perp u$. The constraints on $t_i$ and $v_i$ are $t_i^2 d^2 + \|v_i|^2 \le r_i^2$ and $(1-t_i)^2 d^2 + \|v_i\|^2 \le s_i^2$, and you want to maximize $\|x - y\|^2 = (t_1 - t_2)^2 d^2 + \|v_1 - v_2\|^2$. Clearly it's best to take $v_2$ to be a negative scalar multiple of $v_1$, which makes $\|v_1 - v_2\| = \|v_1\| + \|v_2\|$. So we end up with a four-variable optimization problem (where $w_i = \|v_i\|$):

maximize $(t_1-t_2)^2 d^2 + (w_1 + w_2)^2$ subject to

$t_i^2 d^2 + w_i^2 \le r_i^2$ and $(1-t_i)^2 d^2 + w_i^2 \le s_i^2$, $i=1,2$

which can be handled using the Karush-Kuhn-Tucker equations. There will be several cases to consider.

share|improve this answer
    
Thank you. Looks promising at a first glance. I will have a more in-depth look tomorrow and give feedback accordingly. –  Thilo Schneider May 11 '11 at 18:20
add comment

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.