Practical methods for approximate geometric pattern matching under rigid motions: (preliminary version)

ABSTRACT

We present practical methods for approximate geometric pattern matching in d-dimensions along with experimental data regarding the quality of matches and running times of these methods versus those of a branch-and-bound search. Our methods are faster than previous methods but still produce good matches.

REFERENCES

• 1: Pankaj K. Agarwal , Boris Aronov , Micha Sharir , Subhash Suri, Selecting distances in the plane, Proceedings of the sixth annual symposium on Computational geometry, p.321-331, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98597]
• 2: Helmut Alt , Bernd Behrends , Johannes Blömer, Approximate matching of polygonal shapes (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.186-193, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109669]
• 3: 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]
• 4: E. M. Arkin, K. Kedem, 2. S. B. Mitchell, J. Sprinzak, and M. Werman, "Matching points into pairwisedisjoint noise regions: combinatorial bounds and algorithms,'' ORSA J. Comput., 4(4), 375-38,5, 1992.
• 5: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Wu, An optimal algorithm for approximate nearest neighbor searching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.573-582, January 23-25, 1994, Arlington, Virginia, United States
• 6: L. P. Chew, M. Goodrich, D. Huttenlocher, K. Keclam, J. Kl~inh~rg, and D. Kravets, "Geometric pattern matching under Euclidean motion," in Proc. 5th Canad. Conf. Comput. Geom., Waterloo, Canada, 151-156, 1993.
• 7: L. Paul Chew , Klara Kedem, Improvements on Geometric Pattern Matching Problems, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.318-325, July 08-10, 1992
• 8: R. Cole, "Slowing down sorting networks to obtain faster sorting algorithms," in Proc. ~5th Annu. IEEE Sympos. Found. Comput. Sci., 255-260, 1984.
• 9: Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
• 10: Richard Cole , Jeffrey S. Salowe , W. L. Steiger , Endre Szemerédi, An optimal-time algorithm for slope selection, SIAM Journal on Computing, v.18 n.4, p.792-810, Aug. 1989 [doi>10.1137/0218055]
• 11: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 12: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 13: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: Michael T. Goodrich , Roberto Tamassia, Dynamic trees and dynamic point location, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.523-533, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103472]
• 16: Paul J. Heffernan, Generalized Approzimate Algorithms for Point Set Congruence, Proceedings of the Third Workshop on Algorithms and Data Structures, p.373-384, August 11-13, 1993
• 17: Paul J. Heffernan , Stefan Schirra, Approximate decision algorithms for point set congruence, Proceedings of the eighth annual symposium on Computational geometry, p.93-101, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142697]
• 18: Daniel P. Huttenlocher , Klara Kedem, Computing the minimum Hausdorff distance for point sets under translation, Proceedings of the sixth annual symposium on Computational geometry, p.340-349, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98599]
• 19: Daniel P. Huttenlocher , Klara Kedem , Jon M. Kleinberg, On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane, Proceedings of the eighth annual symposium on Computational geometry, p.110-119, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142700]
• 20: Daniel P. Huttenlocher , Klara Kedem , Micha Sharir, The upper envelope of Voronoi surfaces and its applications, Proceedings of the seventh annual symposium on Computational geometry, p.194-203, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109670]
• 21: K. Imai , S. Sumino , H. Imai, Minimax geometric fitting of two corresponding sets of points, Proceedings of the fifth annual symposium on Computational geometry, p.206-275, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73863]
• 22: Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
• 23: K. Mehlhorn, Multi-dimensional Searching and Computational Geometry, Data Structures and Algorithms, vol. 3, Springer-Verlag, Heidelberg, West Germany, 1984.
• 24: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 25: Günter Rote, Computing the minimum Hausdorff distance between two point sets on a line under translation, Information Processing Letters, v.38 n.3, p.123-127, May 7, 1991 [doi>10.1016/0020-0190(91)90233-8]
• 26: W. Rucklidge, "Lower bounds for the complexity of the Hausdorff distance," in Proc. 5th Canad. Con/. Cornput. Geom., Waterloo, Canada, 145-150, 1993.

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, Experimentation, Verification