Computing the minimum Hausdorff distance for point sets under translation

ABSTRACT

We consider the problem of computing a translation that minimizes the Hausdorff distance between two sets of points. For points in @@@@1 in the worst case there are ⊖(mn) translations at which the Hausdorff distance is a local minimum, where m is the number of points in one set and n is the number in the other. For points in @@@@2 there are ⊖(mn(m + n)) such local minima. We show how to compute the minimal Hausdorff distance in time &Ogr;(mn log mn) for points in @@@@1 and in time &Ogr;(m2n2&agr;(mn)) for points in @@@@2. The results for the one-dimensional case are applied to the problem of comparing polygons under general affine transformations, where we extend the recent results of Arkin et al on polygon resemblance under rigid body motion. The two-dimensional case is closely related to the problem of finding an approximate congruence between two points sets under translation in the plane, as considered by Alt et al.

REFERENCES

• ACHKM: Esther M. Arkin , L. Paul Chew , David P. Huttenlocher , Klara Kedem , Joseph S. B. Mitchell, An efficiently computable metric for comparing polygonal shapes, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.129-137, January 22-24, 1990, San Francisco, California, United States
• AMWW: Helmut Alt , Kurt Mehlhorn , Hubert Wagener , Emo Welzl, Congruence, similarity and symmetries of geometric objects, Discrete & Computational Geometry, v.3 n.3, p.237-256, Jan., 1988 [doi>10.1007/BF02187910]
• At: Atallah, M.J. "A Linear Time Algorithm for the Hausdorff Distance Between Convex Polygons", Information Processing Letters, vol. 17, 207-209, 1983.
• CD: L. Paul Chew , Robert L. (Scot) Dyrsdale, III, Voronoi diagrams based on convex distance functions, Proceedings of the first annual symposium on Computational geometry, p.235-244, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323264]
• EGS: Edelsbrunner, H., Guibas, L.J and Sharir, M. "The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications", Tech. Report UIUCDCDS-R-87-1390, Dept. of Comp. Sci., University of Illinois at Urbana-Champaign, November 1987.
• HKS: Huttenlocher, D.P., Kedem, K. and Sharir, M. "Efficiently Computing the Hausdorff Distance for Point Sets Under Translation", in preparation.
• Ho: Berthold Klaus Paul Horn, Robot vision, MIT Press, Cambridge, MA, 1986
• Kl: Klein, F. Elementary Mathematics from an Advanced Standpoint: Geometry, MacMillan, New York, 1939.
• OS: Mark H. Overmars , Micha Sharir, Merging visibility maps, Proceedings of the sixth annual symposium on Computational geometry, p.168-176, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98561]
• LS: Leven, D. and Sharir, M. "Planning a purely translational motion for a convex polygonal object in two dimensional space using Generalized Voronoi diagrams', Discrete and Computational Geometry, vol 2, pp. 9-31, 1987.
• Me: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• Ro: Royden, H.L. Real Analysis, Macmillan, New York, 1968.
• Sp: Spivak, M. A Comprehensive Introduction to Differential Geometry, Volume 3, Publish or Perish Press, Berkeley Calif., 1979.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

General Terms:
Algorithms