Is there an efficient Hausdorff Distance algorithm? Two sided Hausdorff distance is calculated as 
$$H(r_1,r_2)=\max\{h(r_1,r_2),h(r_2,r_1)\}$$
where
$$h(r_1,r_2)=\max_{a \in r_1}\min_{b\in r_2}\|r_1-r_2\|$$ and vice-verse 
$r_1$ and $r_2$ are two non empty, finite sets
This when programmed will take $O(n^2)$ time
Is there a better algorithm so that the time complexity is reduced? I need this to use in my project for finding the diffence between two images
 A: Suppose you know both sets are in, say, a square of side $L$.  I'm assuming you're using Euclidean distance, but other metrics will be similar.  Break up the square into $m^2$ small squares of side $L/m$ and see which small squares contain members of each set.  If for every small square that contains members of one set, that square or one of its 8 neighbours contains a member if the other set, you know the Hausdorff distance is at most $2 \sqrt{2} L/m$.  On the other hand, if there is a small square that contains members of $r_1$ and 
neither it nor any of its neighbours contains members of $r_2$, you know that the Hausdorff distance is at least the distance from the square to the closest other small square that contains members of $r_2$.  These estimates can then be refined by subdividing the relevant small squares.
A: This answer is biased towards computer programming than mathematics but I could achieve my intended goal: "Reduction in computation time for Hausdorff Distance"
The answer is SIMD technology. I coded this problem using OpenCL on Python by following all your advices. Thank you all for helping me. The complexity is unaltered but the execution time is significantly reduced due to massive parallelism.
