Why this algorithm for computing h(A, B) doesn't work
when A is inside of B or when A partially intersects B
As shown in the applet, the algorithm proposed my M.J. Atallah works in the case where the two polygons are completely separated as well as for computing the Hausdorff distance from a polygon to another polygon that lies completely inside it. But one could be tempted to use it to compute the Hausdorff distance between two convex polygons, regardless of their mutual position. At the end of his paper, M.J. Atallah states that «[...] it is easy to modify our algorithm for the case when the two polygons intersect or when one of them contains the other». We will now show how these two problems differ.
Let's first consider the case when trying to compute the distance from a polygon to another polygon that contains it entirely. By considering a few examples, one will be convinced that the possible candidates for the Hausdorff distance won't be the vertices of the polygon anymore. In fact, the vertices of the polygon will possibly be the candidates for the Hausdorff distance only in specific, degenerate cases. So lemma 2 doesn't hold anymore.
The case of lemma 1 is easier to consider if we use the equivalent characterization we have explained above. When polygon A lies outside of polygon B, the regions we have defined describe the regions of the plane for which the closest point of polygon B is either the vertex defining the sector or on the edge defining the band. But what are these closest-point regions inside of polygon B ? Here the problem is very different since those regions are defined by the medial axis of polygon B. The vertices of polygon A candidates for the Hausdorff distance are now the intersection points of polygon A with the medial axis of polygon B.
So if we were to modify our algorithm to make it work in this case, we would have to consider all the intersection points of polygon A with the medial axis of polygon B, and check the distance of these points to the edge of B that define the medial axis cell in which we currently lie. But unlike the first case, where all regions were completely ordered around polygon B, the medial axis cells have no complete order. In the first case, where polygon A was outside polygon B, a point that traveled on the boundary of polygon A would cross all the regions in order. Here on the other hand, we can devise cases where a medial axis cell can have order n neighbor regions. This shows how different the problem is when we consider the interior of polygon B instead of its exterior.