Chris Crutchfield
This is an implementation of the (1+ε)-approximation algorithm for the directed Hausdorff under translation problem (found on slide 13 of the notes from lecture #21). This approximation algorithm does the following. For point sets A and B in the plane such that there exists a translation t with DH(t(A),B) ≤ r, it finds a translation t' such that DH(t'(A),B) ≤ (1+ε)r. DH is the directed Hausdorff distance, defined as DH(A,B) = maxa ∈ A minb ∈ B ||a - b||2.
This applet is fairly simple to use. You may input points by clicking, and you can drag and move points by selecting them. Once you input as many points as you want for the set A, press the Enter key to enter points for set B. At this point you should type in the desired radius (note that the radius determines what ε is, since the display is already gridded with width εr). Once you've entered enough points so that |A| = |B|, the applet will compute an approximation of the correct translation.
You may restart the applet at any time by pressing the Delete key.