Before revision:  For point sets of size n and m, the Hausdorff distance under translation can be computed in time \tilde O(nm) for the L_1 and L _\inf norm [Chew, Kedem SWAT'92] and \tilde O(nm (n+m)) for the L_2 norm [Huttenlocher, Kedem, Sharir DCG'93].
After revision:  For point sets of size n and m, the Hausdorff distance under translation can be computed in time \tilde O(nm) for the L_1 and L _\infty norm [Chew, Kedem SWAT'92] and \tilde O(nm (n+m)) for the L_2 norm [Huttenlocher, Kedem, Sharir DCG'93].