# Hausdorff distance via support function

Let $A$ and $B$ be convex compact sets in $\mathbb{R}^n$. Define $$h_{+}(A,B) = \inf \left\{ \varepsilon > 0 \mid A \subseteq B+\mathbb{B}_{\varepsilon} \right\}$$ where $\mathbb{B}_{\varepsilon}$ is an $\varepsilon$-ball centered at origin. Hausdorff distance between $A$ and $B$ is $$h(A,B) = \max \left\{ h_{+}(A,B), h_{+}(B,A) \right\}$$ Support function of a compact convex set $K$ is defined as $$c(y\mid K) = \max\limits_{x \in K} \langle y, x\rangle$$ How to show that $$h(A,B) = \max\limits_{ | y | \leq 1} | c(y \mid A) - c (y \mid B) |$$ I tried to use the Legendre transform but without success.

-
I recently sketched a proof in my blog: calculus7.org/2012/05/06/pick-a-point-any-point –  user31373 Jun 13 '12 at 22:20
Yeah, thanks, I did it. –  Nimza Jun 14 '12 at 16:08
Lemma. $h_{+}(A,B) = \sup\limits_{a \in A}\; \mathop{\mathrm{dist}}{(a,B)}$.
Proof. $$h_{+}(A,B) \leq \varepsilon \Leftrightarrow A \subseteq B+\mathbb{B}(\varepsilon,0) \Leftrightarrow \forall a \in A \; (a \in B+\mathbb{B}(\varepsilon,0)) \\ \Leftrightarrow \forall a \in A \; \exists b\in B \colon|b-a|\leq\varepsilon \Leftrightarrow \forall a \in A \; \mathop{\mathrm{dist}}{(a,B)} \leq \varepsilon \\ \Leftrightarrow \sup\limits_{a \in A} \; \mathop{\mathrm{dist}}(a,B) \leq \varepsilon.$$ Since $h_{+}(A,B) \leq \varepsilon$ iff $\sup_{a \in A} \; \mathop{\mathrm{dist}}(a,B) \leq \varepsilon$ they are equal. $\blacksquare$
Hence we have an equality $$h(A,B) = \max \left\{ \sup\limits_{a \in A} \; \mathop{\mathrm{dist}}(a,B), \; \sup\limits_{b \in B} \; \mathop{\mathrm{dist}}(b,A) \right\}.$$ Recall that convex conjugate function of $x \mapsto \mathop{\mathrm{dist}}(x,B)$ is a support function of compact convex set $B$, i.e. $$d(a,B) = \sup\limits_{\|l\| \leq 1} \left( \langle l, a \rangle - c(l \mid B) \right).$$ Now we are ready to proove our main formula. We have $$\sup\limits_{a \in A} \;\mathop{\mathrm{dist}}(a,B) = \sup\limits_{a \in A} \sup\limits_{\|l\| \leq 1} ( \langle l, a \rangle - c(l \mid B) ) = \sup\limits_{\|l\| \leq 1} ( c(l \mid A) - c (l \mid B) ).$$ We have changed the order of supremums in the latter equality. Now since $$\sup\limits_{\|l\| \leq 1} | c(l \mid A) -c (l \mid B) | = \max \{ \sup\limits_{\|l\| \leq 1} ( c(l \mid A) - c (l \mid B) ), \sup\limits_{\|l\| \leq 1} ( c(l \mid B) - c (l \mid A) ) \}$$ we obtain the needed formula: $$h(A,B) = \sup\limits_{\|l\| \leq 1} | c(l \mid A) -c (l \mid B) |.$$