# 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

-
What is the norm here? are the objects in $r$ vectors? in what space? what dimension? – Bitwise Oct 19 '12 at 18:52
r is a 2D array or a 2D matrix of binary image, hence i will be calculating the Hausdorff Distance using the position of the pixels rather than the value of the pixels. – Yash Oct 19 '12 at 18:59

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.