# Computation of the Hausdorff Distance between Two Compact Convex Sets
## Appendix A  
### Proofs  
**Proposition A1**.: _If \(A\) and \(B\) are balls with radii \(r_{A}\) and \(r_{B}\) and centers \(\mathbf{c}_{A}\) and \(\mathbf{c}_{B}\), respectively, then \(\operatorname{dist}(\mathbf{x},B)=\|\mathbf{x}-\mathbf{c}_{B}\|-r_{B}\) for \(\mathbf{x}\
ot\in B\), and \(d(A,B)=\|\mathbf{c}_{A}-\mathbf{c}_{B}\|+r_{A}-r_{B}\), unless \(A\subset B\), in which case the maximum is \(0\)._  
Proof.: The first assertion is obvious. To maximize \(\operatorname{dist}(\mathbf{x},B)\) over \(A\), we form the Lagrangian  
\[\mathcal{L}(\mathbf{x},\lambda) = -\frac{1}{2}\|\mathbf{x}-\mathbf{c}_{B}\|^{2}+\frac{1}{2}\lambda(\|\mathbf{x }-\mathbf{c}_{A}\|^{2}-r_{A}^{2}).\]  
The stationary condition  
\[\mathbf{0} = -\mathbf{x}+\mathbf{c}_{B}+\lambda(\mathbf{x}-\mathbf{c}_{A})\]  
implies that  
\[\mathbf{x}-\mathbf{c}_{A} = \frac{\mathbf{c}_{B}-\lambda\mathbf{c}_{A}}{1-\lambda}-\mathbf{c}_{A} = \frac{(\mathbf{c}_{B}-\mathbf{c}_{A})}{1-\lambda}\]  
and determines \(\lambda\) through  
\[r_{A}^{2} = \frac{\|\mathbf{c}_{B}-\mathbf{c}_{A}\|^{2}}{(1-\lambda)^{2}}.\]  
It follows that  
\[\mathbf{x} = \mathbf{c}_{A}\pm r_{A}\frac{(\mathbf{c}_{B}-\mathbf{c}_{A})}{\|\mathbf{c}_{B}- \mathbf{c}_{A}\|}\]  
and that  
\[\operatorname{dist}(\mathbf{x},B) = \|\mathbf{x}-\mathbf{c}_{B}\|-r_{B}\] \[= \|\mathbf{c}_{A}-\mathbf{c}_{B}\pm r_{A}\frac{(\mathbf{c}_{B}-\mathbf{c}_{A})}{ \|\mathbf{c}_{B}-\mathbf{c}_{A}\|}\|-r_{B}\] \[= \left|1\mp\frac{r_{A}}{\|\mathbf{c}_{A}-\mathbf{c}_{B}\|}\right|\|\|\mathbf{c }_{A}-\mathbf{c}_{B}\|-r_{B}.\]  
Geometrically, \(\max_{\mathbf{x}\in A}\operatorname{dist}(\mathbf{x},B)=\|\mathbf{c}_{A}-\mathbf{c}_{B}\|+r_ {A}-r_{B}\) should hold, so \(\mathbf{x}=\mathbf{c}_{A}-r_{A}\frac{(\mathbf{c}_{B}-\mathbf{c}_{A})}{\|\mathbf{c}_{B}-\mathbf{c}_{A }\|}\) gives the correct sign.  
**Proposition A2**.: _If \(A\) is the probability simplex in \(\mathbb{R}^{p}\) and \(B\) is the \(\ell_{1}\) ball \(U\) translated by \(\mathbf{1}\), then \(d_{H}(A,B)=\sqrt{p}\)._  
Proof.: Consider first \(d(A,B)\). The maximum of \(d(\mathbf{x},B)\) occurs at an extreme point of \(A\), say \(\mathbf{x}=(1,0,\ldots,0)^{\top}=\mathbf{e}_{1}\) by symmetry. On \(U\) the convex function  
\[f(\mathbf{y}) = \|\mathbf{y}+\mathbf{1}-\mathbf{e}_{1}\|^{2}\ \ =\ \ y_{1}^{2}+\sum_{i>1}(y_{i}+1)^{2}\]  
achieves its minimum value when all \(y_{i}\) are equal for \(i>1\). The common value \(z\) should satisfy \(z\leq 0\), while \(y_{1}\) can have either sign. For \(y_{1}\in[0,1]\), we accordingly minimize \(y_{1}^{2}+(p-1)(z+1)^{2}\) subject to \(y_{1}-(p-1)z\leq 1\). We can decrease \(z\) until \(y_{1}-(p-1)z=1\) and solve for \(z=\frac{y_{1}-1}{p-1}\). Thus, we must minimize \(q(y_{1})=y_at either 0 or 1. Because \(q(0)=\frac{(p-2)^{2}}{(p-1)}\) and \(q(1)=1+p-1=p\), the point 0 wins, and \(d(A,B)=\sqrt{\frac{(p-2)^{2}}{p-1}}\).  
Next, consider \(d(B,A)\). The maximum of \(d(\mathbf{y},A)\) occurs at an extreme point of \(B\), say \(\mathbf{y}=\pm\mathbf{e}_{1}+\mathbf{1}\) by symmetry. On \(A\) the convex function  
\[f(\mathbf{x}) = \|\mathbf{x}-\mp\mathbf{e}_{1}-\mathbf{1}\|^{2}\ \ =\ \ (x_{1}\mp 1-1)^{2}+\sum_{i>1}(x_{i}-1)^{2}\]  
is maximized by taking \(\mathbf{y}=\mathbf{e}_{1}+\mathbf{1}\). We make this choice and again assume \(x_{i}=z\) for \(i>1\). Now \(z\geq 0\), and we increase \(z\) until \(x_{1}+(p-1)z=1\). This gives \(z=\frac{1-x_{1}}{p-1}\) and reduces \(f(\mathbf{x})\) to the quadratic  
\[q(x_{1}) = x_{1}^{2}+(p-1)\frac{(2-p-x_{1})^{2}}{(p-1)^{2}}.\]  
Now the stationary point \(-\frac{p-2}{p}\) of \(q(x_{1})\) falls outside \([0,1]\), so the minimum occurs at either 0 or 1. Thus, \(q(0)=\frac{(p-2)^{2}}{p-1}\) and \(q(1)=1+p-1=p\), and the point 1 wins. Finally, \(d_{H}(A,B)=\max\left\{\sqrt{\frac{(p-2)^{2}}{(p-1)}},\sqrt{p}\right\}=\sqrt{p}\).