Re: Lemma 4.14 of Computational Geometry by Mark de Berg et al.

93 Views Asked by At

Construction

Assume that there are two distinct discs $D_0$ and $D_1$, of same radius, in $\mathbb{R}^2$ with centers $x_0$ and $x_1$, respectively, such that $D_0 \cap D_1 \neq \emptyset$. We define a family of discs $\{D(\lambda) | 0 \leq \lambda \leq 1\}$ as follows: Let $z$ be an intersection point of $\partial D_0$ and $\partial D_1$, the boundaries of $D_0$ and $D_1$. The center of $D(\lambda)$ is the point $x(\lambda ) := (1 − \lambda )x_0 + \lambda x_1$, and the radius of $D(\lambda)$ is $r(\lambda) := d(x(\lambda), z)$.

Claim

$D_0 \cap D_1 \subset D(\lambda)$ for all $\lambda \in [0,1]$.

diagram

Questions

The claim appears to be simple. But I can't prove it.

Is the claim true (with similar construction) when $D_0$ and $D_1$ are of different size?

Is the claim true (with similar construction) for higher (finite) dimensions?

1

There are 1 best solutions below

0
On BEST ANSWER

I have an answer for the two-dimensional case. Without restricting generality suppose that the disks are given by $x^2 + y^2 \leq r^2$ and $(x - a)^2 + y^2 \leq r^2$ for some $0 < a < 2r$. In this case $x(\lambda) =\lambda a$ and $r(\lambda) = \sqrt{r^2 + a^2\lambda(\lambda - 1)}$. If $(x,y)\in D_0\cap D_1$, then

$$ y = \pm\left\{ \begin{array}{ll} \sqrt{r^2 - x^2}, & a/2 \leq x \leq r\\[1mm] \sqrt{r^2 - (x - a)^2}, & a - r \leq x \leq a/2 \end{array} \right. $$

Now consider the distance $d(x,y)$ from $(\lambda a,0)$ to any point in $D_0\cap D_1$. If $a/2 \leq x \leq r$, then

$$ d(x,y) = \sqrt{r^2 + \lambda a(\lambda a - 2x)} \leq \sqrt{r^2 + \lambda a^2(\lambda - 1)} = r(\lambda). $$

Similarly, if $a - r \leq x \leq a/2$, then

$$ d(x,y) = \sqrt{r^2 + (1-\lambda) a(2x - (\lambda+1)a)} \leq \sqrt{r^2 + \lambda a^2(\lambda - 1)} \leq r(\lambda) $$

Thus, it follows that $D_0\cap D_1 \subset D(\lambda)$. I believe this result could be extended to higher dimensions, although I haven't thought about that yet.