Home Bookmarks Papers Blog

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 Rd, 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 Rd 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.

Postscript, PDF.

@string{SOCG_2003 = "Proc. 19th Annu. ACM Sympos. Comput. Geom."}

  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/}

Last modified: Thu Jun 12 16:35:43 CDT 2003