Upper bound for the Hausdorff distance

Last week I was working on the project “Robust computation of the Hausdorff distance between triangle meshes” under Dr. Leonardo Sacht’s supervision with TA Erik Amezquita and SGI fellows Bryce Van Ross and Deniz Ozbay. 

If we have triangle meshes \( A, B \), then \( h(A,B) = \max_{p \in A}d(p,B) \) is called the Hausdorff distance from \( A\) to \( B \), where \(d\) is Euclidean distance. In general case, this function is not symmetric, so the final metric is defined as \(H(a,b) = \max(h(A,B), h(B,A))\).

The Hausdorff distance is very significant in Geometry Processing on the grounds that it may be used for determining the difference between two meshes. The method that we are studying is called the “branch-and-bound” method. The main idea is to calculate the common lower bound for distance from the whole mesh \( A\) to mesh \(B\) and individual upper bounds for distances from every triangle mesh \(T_{A}\) of mesh \( A \) to mesh \(B\). If the upper bounds of some triangles is smaller than the lower bound, then we throw them away and consider the remaining subdivided ones.

My task was to code the function that returns the upper bounds for distances from every triangle mesh \(T_{A}\) of mesh \( A \) to mesh \(B\). We are going to use the distances between vertices of triangle mesh \(T_{A}\) and triangle inequality to find the upper bound: \[u( T_{A}, B) = \max_{j = 1}^{3}(\max(|v_{j} – v_{j + 1}|, |v_{j} – v_{j + 2}|) + \min_{b \in B}(|v_{j} – b|))\] where \(v_{1}, v_{2}, v_{3}\) are the vertices of triangle mesh \(T_{A}\) .

This is how the implemented algorithm looks like in Matlab:

I really enjoyed working on the project this week with my team, TA and supervisor. I am looking forward to continuing work and improving what we have already done.