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 1 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). $$ 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) |. $$

share|improve this answer

Your Answer


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.