# Computation of the Hausdorff Distance between Two Compact Convex Sets
## 4 Discussion

Table 1: Computation of \(d_{H}(A,B)\) by various methods. to be limited to random point clouds. Infinite sets defined by mathematical formulas have been largely ignored. The current paper partially rectifies this omission and demonstrates the value of continuous optimization techniques. The Frank-Wolfe and projected gradient ascent algorithms are relatively easy to code and extremely fast, even in high dimensions. Our preliminary experiments tilt toward projected gradient ascent as the more reliable of the two options. A naive implementation of the point-cloud method is not remotely competitive with projected gradient ascent. More exhaustive studies are warranted beyond the proof of principle examples presented here. The standard convergence arguments covered in Section 2.6 guarantee that all limit points of the two algorithm classes are stationary points. In practice, convergence appears much faster than the slow rates mentioned in Propositions 1 and 2. We suspect, but have not proved, that full convergence to a stationary point always occurs. This exercise would require a foray into the difficult terrain of real algebraic geometry [40]. In any event, convergence to a global maximum is not guaranteed. Fortunately, safeguards can be put in place to improve the chances of successful convergence. The homotopy method capitalizes on the exact distance between two balls. Minkowski set rounding smooths the boundary of the target sets and steers iterates in a productive direction. The computation of the Hausdorff distance \(d_{H}(A,B)\) is apt to be much more challenging when either \(A\) or \(B\) is non-convex. Many sets can be represented as finite unions of compact convex sets. If \(A=\cup_{i}A_{i}\) and \(B=\cup_{j}B_{j}\), then the computation of \(d_{H}(A,B)\) reduces to the computation of \(d(A_{i},B)\) for each index \(i\) and \(d(B_{i},A)\) for each index \(j\). The identities \(d(A,B)=\max_{i}d(A_{i},B)\) and \(d(B,A)=\max_{i}d(B_{j},A)\) make this claim obvious. The further identity \(\operatorname{dist}(\vec{x},B)=\min_{j}\operatorname{dist}(\vec{x},B_{j})\) implies that  
\[d(A,B) = \max_{i}d(A_{i},B)\]  
\[= \max_{i}\max_{x\in A_{i}}\min_{j}\operatorname{dist}(\vec{x},B_{j}).\]  
In general, saddlepoint problems of this sort are hard to solve. One possible line of attack is to minorize \(\min_{j}\operatorname{dist}(\vec{x},B_{j})\) and then maximize the minorization. The validation and implementation of this strategy will require substantial effort beyond the introduction to the problem pursued in the current paper. Let us merely add that the fast implementation of a more general Hausdorff distance algorithm will depend on the nature of the candidate sets \(A_{i}\) and \(B_{j}\). In the plane, triangles are appealing [41; 42]. It is straightforward to project onto a triangle, and a triangle by definition possesses exactly three extreme points. Furthermore, a great deal of research under the heading of finite elements has identified good algorithms for triangulating complicated regions of the plane. The software Triangle for generating two-dimensional meshes and Delaunay triangulations is surely pertinent [43]. The triangularization of surfaces forms part of the MESH software for Hausdorff distance estimation [44]. We hope this paper will provoke a greater focus on the Hausdorff distance problem. As a prototype non-convex problem, it is worthy of far more attention. Continuous optimization tools can be brought to bear on the problem and may ultimately generate more efficient algorithms than the discrete algorithms designed for finite point clouds. The fact that our algorithms scale well in higher dimensions is a plus. We would also like to highlight the illumination that the MM principle brings to the construction of new high-dimensional optimization algorithms, including those considered here. Although neglected in the past, MM may well be the single most unifying principle of algorithm construction in continuous optimization. []  
**Funding:** Research supported in part by USPHS grants GM53275 and HG006139.