# Computation of the Hausdorff Distance between Two Compact Convex Sets
## 2 Materials and Methods
### A Homotopy Method  
Although both algorithms are guaranteed to increase the objective, they both suffer from the danger of being trapped by local maxima. One obvious remedy is to launch the algorithms from different random points. A more systematic alternative is to exploit homotopy. The idea is to gradually deform both sets \(A\) and \(B\) from the unit ball \(U\) at the origin, where \(d_{H}(U,U)=0\) is known, into the target sets \(A\) and \(B\). In practice, we follow the solution path along the family of set pairs \([tA+(1-t)U,tB+(1-t)U]\) from \(t=0\) to \(t=1\). This strategy is viable for projected gradient ascent because we can project points onto the Minkowski convex combination \(tC+(1-t)D\) by three devices. First, it is well known that when \(A\) and \(B\) are balls with radii \(r_{A}\) and \(r_{B}\) and centers \(\mathbf{c}_{A}\) and \(\mathbf{c}_{B}\), respectively, the distance \(\operatorname{dist}(\mathbf{x},B)\) is maximized by taking \(\mathbf{x}=\mathbf{c}_{A}-r_{A}\frac{(\mathbf{c}_{B}-\mathbf{c}_{A})}{\|\mathbf{c}_{B}-\mathbf{c}_{A}\|}\), unless \(A\subset B\), in which case the maximum is \(0\)[32]. For the convenience of the reader, Proposition A1 of Appendix A proves this assertion. Second, one can exploit the projection identity \(P_{tS}(\mathbf{z})=tP_{S}(t^{-1}\mathbf{z})\) for any \(t>0\). Third, there is an effective algorithm for projecting onto a Minkowski sum \(C+D\)[33]. The idea is to alternate the minimization of \(\|\mathbf{z}-\mathbf{c}-\mathbf{d}\|\) with respect to \(\mathbf{c}\in C\) and \(\mathbf{d}\in D\). The iteration scheme \(\mathbf{c}_{n+1}=P_{C}(\mathbf{z}-\mathbf{d}_{n})\) and \(\mathbf{d}_{n+1}=P_{D}(\mathbf{z}-\mathbf{c}_{n+1})\) is guaranteed to converge at a linear rate when either set is strongly convex. Recall that a convex \(K\) is strongly convex if there exists an \(r>0\) such that  
\[\alpha\mathbf{x}+(1-\alpha)\mathbf{y}+\frac{r}{2}\alpha(1-\alpha)\|\mathbf{x}-\mathbf{y}\|^{2 }\mathbf{z} \in K\]  
for all \(\mathbf{x}\) and \(\mathbf{y}\) in \(K\), \(\alpha\in[0,1]\), and unit vectors \(\mathbf{z}\)[34]. In particular, \((1-t)U\) is strongly convex when \(t\in[0,1)\). Furthermore, the Cartesian product of two strongly convex sets is strongly convex [35]. The homotopy method succeeds because the early sets are more rounded and the objective generates fewer local maxima. The price for better performance is iterations within iterations and an overall slower algorithm. Algorithms 2 and 3 summarize our homotopy strategy for projected gradient ascent. ```
0: Projection operators \(P_{A}(\mathbf{x})\) and \(P_{B}(\mathbf{y})\), external point \(\mathbf{y}\), convexity constant \(c\), maximum iterations \(n\), and convergence criterion \(\epsilon>0\). 1:\(\mathbf{a}=\mathbf{b}=\mathbf{0}\)
2:for\(iter=1:n\)do
3:\(\mathbf{a}_{\text{new}}=cP_{A}[(\mathbf{y}-\mathbf{b})/c]\)
4:\(\mathbf{b}_{\text{new}}=(1-c)P_{B}[(\mathbf{y}-\mathbf{a}_{\text{new}})/(1-c)]\)
5:if\(\|\mathbf{a}_{\text{new}}-\mathbf{a}\|+\|\mathbf{b}_{\text{new}}-\mathbf{b}\|<\mathbf{\epsilon}\)then
6: break
7:else
8:\(\mathbf{a}=\mathbf{a}_{\text{new}}\)
9:\(\mathbf{b}=\mathbf{b}_{\text{new}}\)
10:endif
11:endfor
12:Return \(\mathbf{a}_{\text{new}}\) and \(\mathbf{b}_{\text{new}}\)
```  
**Algorithm 2** Minkowski Set Projection  
```
0: Projection operators \(P_{A}(\mathbf{x})\) and \(P_{B}(\mathbf{x})\), centers \(c_{A}\) and \(c_{B}\), and homotopy points \(h\).