The question is related to the Hausdorff distance between sets, $d_H(S,S')$, which is the greatest of all the distances from a point in one set to the closest point in the other set.

Suppose there are two sets $S$ and $T$ such that $S\cap T$ has a non-empty interior. Prove that there exists a constant $r>0$, such that every set $S'$ whose Hausdorff distance from $S$ is less than $r$ also intersects $T$.

Here is my attempt:

enter image description here

Let $P$ be a point in the interior of $S\cap T$, and let $r>0$ be the largest radius of a ball contained in $S\cap T$ whose center is $P$. If $d_H(S,S')<r$, then, because $P\in S$, there must be a point $P'\in S'$ such that $d(P,P')<r$. Therefore $P'$ is contained in the ball of radius $r$ contained in $S\cap T$, and thus $P'\in S'\cap T$.

A. Is this proof correct?

B. I am trying to slightly generalize this lemma to: there exists a constant $r>0$, such that every set $S'$ whose Hausdorff distance from $S$ is less than $r$ intersects every set $T'$ whose Hausdorff distance from $T$ is less than $r$. Is this generalization correct?

up vote 2 down vote accepted

A. Your proof is correct.

B. No, this generalization is false. In $\mathbb R^n$, given two nonempty compact sets $S$ and $T$ and a number $r>0$, we can find two nonempty compact sets $S'$ and $T'$ such that $d_H(S,S')\le r$, $d_H(T,T')\le r$, and $S'\cap T'=\varnothing$.

Indeed, since $S$ is compact, for any $\epsilon>0$ we can find a finite $r/2$-net $N_S\subset S$, i.e., a set such that for every $x\in S$ there is $y\in N_S$ such that $|x-y|\le r/2$. Observe that $d_H(S,N_S)\le r/2$.

Similarly, let $N_T$ be a $r/2$-net in $T$. If $N_S$ and $N_T$ are disjoint, we are done. Otherwise, move each points of $N_T$ that belongs to $N_S$ in some direction by distance $\le r/2$, so that the new point is not in $N_S$. (Since $N_S$ is finite, this is easy to do). This perturbation creates a set $\tilde N_T$ which is disjoint from $N_S$ and satisfies $d_H(T,\tilde N_T)\le r$.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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