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.
Convex Analysis – Calculating Hausdorff Distance via Support Function
convex-analysis
Related Solutions
1. Yes, this is true. This can be derived from the involutive property of the Legendre-Fenchel transform: if $f:\mathbb R^n\to (-\infty,+\infty]$ is a closed convex function, then $f^{**}=f$ (Theorem 12.2 in Rockafellar's Convex Analysis). Recall that $$f^*(x) = \sup\{\langle x,y\rangle - f(y) : y\in\mathbb R^n\}$$ and a convex function is closed if its epigraph is.
With every convex closed set $K$ we can associate a closed convex function $\delta_K$ by letting $\delta_K(x)=0$ when $x\in K$ and $\delta_K(x)=+\infty$ otherwise. Observe that $\delta_K^*$ is exactly $h_K$.
Given $h$ as in your question, define $K= \{x : \langle x,y\rangle \le h(y) \ \forall y\}$. Observe that $h^*(x)=0$ when $x\in K$, because the supremum is attained by $y=0$. If $x\notin K$, then there is $y$ such that $\langle x,y\rangle > h(y)$. Considering large multiples of such $y$, we conclude that $h^*(x)=\infty$.
Thus, $h^* = \delta_K$. By the involutive property, $h=h^{**} = \delta_K^* = h_K$.
By the way, this result is Theorem 13.2 in Rockafellar's book.
2. Yes, this is correct. Another way to state this fact: the epigraph of $h_{K_1\cap K_2}$ is the convex hull of $\operatorname{epi} h_{K_1} \cup \operatorname{epi} h_{K_2}$. To see this, observe that the epigraph of $h_K$ is determined by its intersection with the horizontal plane $z=1$. This intersection is nothing but $K^\circ$, the polar of $K$. It remains to use the fact that $(K_1\cap K_2)^\circ = \operatorname{conv}(K_1^\circ \cup K_2^\circ)$. See also Corollary 16.5.1 in Rockafellar's book.
\begin{align} \newcommand{\R}{{\mathfrak{R}}} \end{align}
It might help to consider the indicator function. Also we will use the convention that column vectors are elements of $\R^d$ and row vectors are elements of the dual space $(\R^d)^*$ (even though $(\R^d)^*\cong \R^d$).
When $K\subseteq\R^d$ is a nonempty, closed and convex cone, then the support function $\sigma_K:(\R^d)^*\to\R\cup\{+\infty\}$ coincides with the conjugate function of the indicator of $K$ given by $\delta_K:\R^d\to\R\cup\{+\infty\}$ $$ \delta_K(x) = \begin{cases} 0,&\text{if $x\in K$} \\ +\infty,&\text{o.w.}\end{cases} = \delta_{K^\circ} $$ That is, $\sigma_K(\bullet) = \delta_K^*(\bullet) = \sup_x\{\bullet\cdot x - \delta_K(x)\} = \sup_{x\in K} \{\bullet \cdot x\}$. We can also see that $\sigma_K = \delta_{K^\circ}$ where $K^\circ = \{y:y\cdot x \leq 0,;\forall x\in K\}$ is the polar cone of $K$.
When $f$ is convex and smooth, then for any $y\in(\R^d)^*$, $f^*(y)$ can be interpreted as the signed distance between zero and the intercept of a supporting hyperplane of $f$ with slope $y$. We have this interpretation since in this special case, the slope of $f$ is monotone and hence there is a 1:1 map slopes $y$ and points $x$ (see here). However, when $f$ is not convex, we don't have this relationship, so the $\sup$ is taken to make this relationship well-defined.
We're in the latter case when $f=\delta_K$, which is nonconvex, and the only supporting hyperplane of $\delta_K$ is $y=0$ when $x\in K$ (if $x\notin K$, then there are no supporting hyperplanes). It helps to draw this out in 1d, for example with $K=\{x\in\R:x\geq0\}$ (see below).
This means that for any $y\in(\R^d)^*$, we can only interpret $\sigma_K(y)$ as the signed distance to zero of a supporting hyperplane for $\delta_K$ when $y=0$ and $x\in K$. Otherwise, there are no supporting hyperplanes, so the signed distance should be $+\infty$.
Best Answer
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). $$