3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. Looks promising at a first glance. I will have a more in-depth look tomorrow and give feedback accordingly. $\endgroup$ – Thilo Schneider May 11 '11 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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