MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

enter image description here

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|cite|improve this question
up vote 3 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|cite|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

Your Answer


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.