3
$\begingroup$

Definition: The Hausdorff distance associated with a distance $d$ on a space $E$ between two sets $A\subset E$ and $B \subset E$ is $d_H(A, B) = \max(\sup_{x\in B}\{d(x, A)\}, \sup_{y\in A}\{d(y, B)\})$, i.e. this is the maximum distance any point of A can be from B and vice versa.

Question: For a fixed dimension $d$, consider a sequence of convex sets $A_n \subset \mathbb{R}^d$ and a convex set $A \subset \mathbb{R}^d$ such that $d_H(A_n, A) \to 0$ when $n \to \infty$.

Does $d_H(A_n^c, A^c) \to 0$ when $n\to \infty$ ? ($A^c$ denotes the complementary set of $A$)

$\endgroup$

1 Answer 1

3
$\begingroup$

Yes. For each unit vector $v$ in $\mathbb{R}^d$ and for any set $B \subseteq \mathbb{R}^d$, let $$r(B,v) = \inf_{b \in B} \langle b,v\rangle,$$ where $\langle x, y \rangle$ is the inner product of $x$ and $y$. It is not too hard to show that for any $B,C \subseteq \mathbb{R}^d$, $$|r(B,v) - r(C,v)| \leq d_H(B,C),$$ with the appropriate conventions regarding $\infty$.

First I will argue in the case where the $A_n$'s and $A$ are closed convex sets, and then I will extend this to arbitrary convex sets.

For any closed convex set $B$, we have that $$B = \bigcap_{v\text{ unit vector}} \{x \in \mathbb{R}^d : \langle x, v\rangle \geq r(B,v)\}.$$ Let $H(r,v)$ denote the set $\{x \in \mathbb{R}^d : \langle x, v \rangle < r\}$. We clearly have that $B^c = \bigcup_{v\text{ unit vecotr}} H(r(B,v),v)$. It's also not too hard to see that for any fixed unit vector $v$, $d_H(H(r,v),H(r',v)) = |r-r'|$.

Now the crux is this: The Hausdorff metric 'commutes' with arbitrary unions in the following sense, if $\{B_i\}_{i \in I}$ and $\{C_i\}_{i \in I}$ are arbitrary families of sets such that $d_H(B_i,C_i) \leq \varepsilon$ for every $i \in I$, then $d_H\left( \bigcup_{i \in I} B_i, \bigcup_{i \in I} C_i) \right) \leq \varepsilon$.

This means that for each $n$, we have that $$ d_H(A^c_n ,A^c) = d_H\left(\bigcup_{v\text{ unit}}H(r(A_n,v),v), \bigcup_{v\text{ unit}}H(r(A,v),v) \right) \leq \sup_{v\text{ unit}}d_H(H(r(A_n,v),v),H(r(A,v),v)) = \sup_{v\text{ unit}} |r(A_n,v)-r(A,v)| \leq d_H(A_n,A).$$ So we have that $d_H(A_n^c,A^c)$ goes to $0$ as well.

For arbitrary sequences of convex sets, we just need the following facts:

  • For any set $B$, $d_H(B,\overline{B}) = 0$, where $\overline{B}$ is the closure of $B$.
  • For any convex set $B \subseteq \mathbb{R}^d$, $d_H(B^c, \overline{B}^c) = 0$.

The first fact is standard. The second is not too hard but requires a little bit of proof.

$\endgroup$
3
  • $\begingroup$ Thanks for your very clear answer (it took me a bit of time to grasp it). I'm a bit puzzled by the "commutativity" of Hausdorff distance and union, this propery depends on the indexation of the union then, right ? Would you have any good reference for me to dig ? $\endgroup$
    – Pohoua
    Mar 25, 2021 at 1:18
  • 1
    $\begingroup$ It does depend on the indexing, yes. I don't know of a good reference, but it's fairly easy to prove directly. I can add it to the answer if you like. $\endgroup$ Mar 25, 2021 at 15:28
  • $\begingroup$ It's okay I managed to proved it, indeed it's not that hard. Thanks! $\endgroup$
    – Pohoua
    Mar 26, 2021 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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