

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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


