# 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

## 2 Answers

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.

-
Thank you very much. I will apply this. And I will be using Taxi Cab distance instead of Euclidean distance but as you stated, it will be similar. – Yash Oct 19 '12 at 19:31

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.

-