# Computation of the Hausdorff Distance between Two Compact Convex Sets
## 1 Introduction  
The Hausdorff distance [1; 2] between two compact sets \(A\) and \(B\) in a Euclidean space \(\mathbb{R}^{p}\) is defined as  
\[d_{H}(A,B) = \max\{d(A,B),d(B,A)\},\]  
where  
\[d(A,B) = \max_{\boldsymbol{x}\in A}\operatorname{dist}(\boldsymbol{x},B), \quad d(B,A) = \max_{\boldsymbol{x}\in B}\operatorname{dist}(\boldsymbol{x},A),\]  
\[\operatorname{dist}(\boldsymbol{x},A)=\min_{\boldsymbol{y}\in A}\| \boldsymbol{x}-\boldsymbol{y}\|,\text{ and }\operatorname{dist}(\boldsymbol{x},B)=\min_{ \boldsymbol{y}\in B}\|\boldsymbol{x}-\boldsymbol{y}\|\]  
. Here, \(\|\cdot\|\) denotes the standard Euclidean norm in \(\mathbb{R}^{p}\). The Blaschke formula  
\[d_{H}(A,B) = \max_{\boldsymbol{x}}|\operatorname{dist}(\boldsymbol{x},A)- \operatorname{dist}(\boldsymbol{x},B)|\]  
serves as an alternative definition of Hausdorff distance [3]. Wikipedia has a helpful entry on Hausdorff distance with a two-dimensional illustration. The theoretical value of Hausdorff distance stems from the fact that it turns the collection of compact sets into a complete separable metric space. In general, Hausdorff distance is challenging to compute. Hausdorff distance has many applications. For instance, it is instrumental in defining continuity, compactness, and completeness for integral operators, differential operators, and Fourier transforms in functional analysis [4; 5]. These concepts are in turn relevantto the analysis of the existence, uniqueness, and stability of solutions to various equations in mathematics and physics [6]. In computer vision, Hausdorff distance enables object recognition [7] and allows one to quantify the difference between two different representations of the same object [8]. Edge detection and pixelization are usually necessary preprocessing steps. Other applications include robotics [9], the fractal modeling of biological structures [10], and the numerical computation of attractors in dynamical systems [11]. The current paper derives and tests two new algorithms for computing the distance \(d_{H}(A,B)\) between two compact convex sets. The previous work on this intrinsically interesting problem is mostly limited to finite point clouds, usually in two and three dimensions [12; 13; 14; 15; 16]. The formulas  
\[d(A,B) = \max_{\mathbf{x}\in A}\min_{\mathbf{y}\in B}\|\mathbf{x}-\mathbf{y}\|\quad\text{ and}\quad d(B,A) = \max_{\mathbf{x}\in B}\min_{\mathbf{y}\in A}\|\mathbf{x}-\mathbf{y}\|\]  
can be naively implemented for finite sets \(A\) and \(B\). The naive implementation benefits from fast software such as the Julia Distances package, which exploits matrix multiplication to find all Euclidean distances between the column vectors of two matrices. The ImageDistances.jl package (github.com/JuliaImages/Images.jl) appears to rely on the naive method [12] for computing Hausdorff distances. Once the distances \(d_{ij}=\|\mathbf{x}_{i}-\mathbf{y}_{j}\|\) are computed, the computational complexity of the naive method is \(O(mn)\), where \(m\) and \(n\) equal the number of points \(\mathbf{x}_{i}\in A\) and \(\mathbf{y}_{j}\in B\), respectively. This complexity can be reduced by various devices, as suggested in the cited references. The algorithms for computing the Hausdorff distance between two polygons [17], two curves [18] in the plane, and a curve and a surface [19] represent exceptions to the discrete point-cloud method. More complicated sets defined by algebraic formulas can be attacked by pixelating the sets or sampling them at a dense set of random points. The methods of continuous optimization offer an attractive alternative to the various current methods. Although the calculation of \(d_{H}(A,B)\) takes us outside the comfortable realm of convex optimization, the tools of convex calculus are highly pertinent. To their credit, these tools perform well in higher dimensions. It remains to be seen whether the Hausdorff distance will have practical value in shape recognition in this regime. It would be prudent to keep the possibility in mind.