Hausdorff Distance under Translation for Points, Disks,
and Balls

Pankaj K. Agarwal,
Sariel Har-Peled,
Micha Sharir,
and
Yusu Wang

Let A and B be two sets of balls in
R^{d}, d=2,3. We measure similarity between
A and B by computing the minimum Hausdorff distance
between A+t and B, where the minimum is taken either
over all vectors t in R^{d} or over the vectors
t such that A+t and B do not intersect. These
problems arise in measuring similarity between the shapes of two
proteins. We propose a number of exact and approximation algorithms
for these problems. Since Hausdorff distance is sensitive to
out-liers, we also propose efficient approximation algorithms for
computing the minimum root-mean-square(rms) Hausdorff distance, under
translation, between two point sets.

@string{SOCG_2003 = "Proc. 19th Annu. ACM Sympos. Comput. Geom."}
@InProceedings{ahsw-hdtpd-03,
author = {P. K. Agarwal and S.{Har-Peled} and M. Sharir and Y. Wang},
title = {Hausdorff Distance under Translation for Points, Disks,
and Balls},
booktitle = SOCG_2003,
pages = {282--291}
year = 2003,
url = {http://sarielhp.org/research/papers/02/hausdorff/}
}