Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

To prove the above statement we need an additional statement.

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). \tag{1} $$ 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) |. $$

Added. As concerns the proof of (1). Put $f(x) = \mathop{\mathrm{dist}} (x,B)$. Then $$ f^*(l) = \sup_x \bigl( \langle l, x\rangle - f(x) \bigr) \\ = \sup_{b \in B} \sup_x \bigl( \langle l, x\rangle - \|x-b\| \bigr) \\ = \sup_{b \in B} \sup_{\alpha > 0} \sup_{\|x-b\|=\alpha} \bigl( \bigl( \langle l,x-b\rangle - \alpha \bigr) + \langle l, b \rangle \bigr) \\ = \sup_{b \in B} \sup_{\alpha > 0} \bigl( \alpha(\|l\|-1) + \langle l, b\rangle \bigr) \\ = \sup_{b \in B} \bigl( \langle l, b\rangle + \delta_1(\|l\|) \bigr) \\ = c(l|B) + \delta_1(\|l\|), $$ where $\delta_1(t) = 0$ if $t\leq 1$ and $\delta_1(t) = +\infty$ otherwise. Hence, $$ \mathop{\mathrm{dist}} d(x,B) = \sup_l \bigl( \langle l,x\rangle - c(l|B) - \delta_1(\|l\|) \bigr) \\ = \sup_{\|l\|\leq 1} \bigl( \langle l, x \rangle - c(l|B) \bigr). $$

share|improve this answer
    
how did you derive the convex conjugation of $x\longmapsto dist(x, B)$ ? –  Chival Mar 18 at 12:15
1  
@Chival I edited my answer. –  Nimza Mar 18 at 18:45
    
in the last step, did you use the biconjugate theorem(Fenchel-Moreau theorem) ? If so, $f(x)$ should be specified to be convex in particular. In fact, maybe we could use the additivity of support functions to conclude the proof (easier approach): $c(\ell, K + L) = c(\ell, K) + c(\ell, L)$. But your argument works nicely. –  Chival Mar 19 at 21:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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