Exact algorithms for partial curve matching via the Fréchet distance

ABSTRACT

Curve matching is a fundamental problem that occurs in many applications. In this paper, we study the problem of measuring partial similarity between curves. Specifically, given two curves, we wish to maximize the total length of subcurves that are close to each other, where closeness is measured by the Fréchet distance, a common distance measure for curves. The resulting maximal length is called the partial Fréchet similarity between the two input curves.

Given two polygonal curves P and Q in R^d of size m and n, respectively, we present the first exact algorithm that runs in polynomial time to compute f_δ(P, Q), the partial Fréchet similarity between P and Q, under the L₁ and L_∞ norms. Specifically, we formulate the problem of computing f_δ(P, Q) as a longest path problem, and solve it in O(mn(m + n) log(mn)) time, under the L₁ or L_∞ norm, using a "shortest-path map" type decomposition. To the best of our knowledge, this is the first paper to study this natural definition of partial curve similarity in the continuous setting (with all points in the curve considered), and present a polynomial-time exact algorithm for it.

REFERENCES

• 1: P. K. Agarwal, S. Har-Peled, N. Mustafa, and Y. Wang. Near-linear time approximation algorithms for curve simplification in two and three dimensions. Algorithmica, 42:203--219, 2005.
• 2: H. Alt and M. Buchin. Can we compute the similarity between surfaces?, 2007. arXiv:cs/0703011v1.
• 3: Helmut Alt , Alon Efrat , Günter Rote , Carola Wenk, Matching planar maps, Journal of Algorithms, v.49 n.2, p.262-283, November 2003 [doi>10.1016/S0196-6774(03)00085-3]
• 4: H. Alt and M. Godau. Computing the Fréchet distance between two polygonal curves. Internat. J. Comput. Geom. Appl., 5:75--91, 1995.
• 5: H. Alt and L. J. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 121--153. Elsevier Science Publishers B. V. North-Holland, Amsterdam, 2000.
• 6: Helmut Alt , Christian Knauer , Carola Wenk, Matching Polygonal Curves with Respect to the Fréchet Distance, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.63-74, February 15-17, 2001
• 7: Helmut Alt , Christian Knauer , Carola Wenk, Comparison of Distance Measures for Planar Curves, Algorithmica, v.38 n.1, p.45-58, October 2003 [doi>10.1007/s00453-003-1042-5]
• 8: Boris Aronov , Sariel Har-Peled , Christian Knauer , Yusu Wang , Carola Wenk, Fréchet distance for curves, revisited, Proceedings of the 14th conference on Annual European Symposium, p.52-63, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_8]
• 9: Sotiris Brakatsoulas , Dieter Pfoser , Randall Salas , Carola Wenk, On map-matching vehicle tracking data, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 10: K. Buchin , M. Buchin , J. Gudmundsson, Detecting single file movement, Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, November 05-07, 2008, Irvine, California [doi>10.1145/1463434.1463476]
• 11: Kevin Buchin , Maike Buchin , Joachim Gudmundsson , Maarten Löffler , Jun Luo, Detecting Commuting Patterns by Clustering Subtrajectories, Proceedings of the 19th International Symposium on Algorithms and Computation, December 15-17, 2008, Gold Coast, Australia [doi>10.1007/978-3-540-92182-0_57]
• 12: K. Buchin, M. Buchin, C. Knauer, G. Rote, and C. Wenk. How difficult is it to walk the dog? In Proc. 23rd Europ. Workshop Comput. Geom., pages 170--173, 2007.
• 13: Kevin Buchin , Maike Buchin , Carola Wenk, Computing the Fréchet distance between simple polygons, Computational Geometry: Theory and Applications, v.41 n.1-2, p.2-20, October, 2008 [doi>10.1016/j.comgeo.2007.08.003]
• 14: M. Buchin. On the Computability of the Fréchet Distance Between Triangulated Surfaces. PhD thesis, Dept. of Comput. Sci., Freie Universität Berlin, 2007.
• 15: David E. Cardoze , Leonard J. Schulman, Pattern Matching for Spatial Point Sets, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.156, November 08-11, 1998
• 16: Erin Wolf Chambers , Éric Colin de Verdière , Jeff Erickson , Sylvain Lazard , Francis Lazarus , Shripad Thite, Walking your dog in the woods in polynomial time, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA [doi>10.1145/1377676.1377694]
• 17: Axel Mosig , Michael Clausen, Approximately matching polygonal curves with respect to the Fréchet distance, Computational Geometry: Theory and Applications, v.30 n.2, p.113-127, February 2005 [doi>10.1016/j.comgeo.2004.05.004]
• 18: A. F. Cook and C. Wenk. Geodesic Fréchet distance inside a simple polygon. In Proc. 25th Internat. Sympos. Theoret. Asp. Comp. Sci., pages 193--204, 2008.
• 19: Alon Efrat , Quanfu Fan , Suresh Venkatasubramanian, Curve Matching, Time Warping, and Light Fields: New Algorithms for Computing Similarity between Curves, Journal of Mathematical Imaging and Vision, v.27 n.3, p.203-216, April 2007 [doi>10.1007/s10851-006-0647-0]
• 20: A. Efrat, S. Har-Peled, L. J. Guibas, J. S. Mitchell, and T. Murali. New similarity measures between polylines with applications to morphing and polygon sweeping. Discrete Comput. Geom., 28:535--569, 2002.
• 21: Piotr Indyk, Approximate nearest neighbor algorithms for Frechet distance via product metrics, Proceedings of the eighteenth annual symposium on Computational geometry, p.102-106, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513414]
• 22: Piotr Indyk , Rajeev Motwani , Suresh Venkatasubramanian, Geometric matching under noise: combinatorial bounds and algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.457-465, January 17-19, 1999, Baltimore, Maryland, United States
• 23: Eamonn J. Keogh , Michael J. Pazzani, Scaling up Dynamic Time Warping to Massive Dataset, Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, p.1-11, September 15-18, 1999
• 24: Man-Soon Kim , Sang-Wook Kim , Miyoung Shin, Optimization of subsequence matching under time warping in time-series databases, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066814]
• 25: R. Kolodny, P. Koehl, and M. Levitt. Comprehensive evaluation of protein structure alignment: Scoring by geometric measures. J. Mol. Biol., 346:1173--1188, 2005.
• 26: S. Kwong, Q. H. He, K. F. Man, K. S. Tang, and C. W. Chau. Parallel genetic-based hybrid pattern matching algorithm for isolated word recognition. Int. J. Pattern Recognition & Artificial Intelligence, 12(5):573--594, August 1998.
• 27: J. S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, chapter 15, pages 633--701. Elsevier, 2000.
• 28: M. Parizeau , R. Plamondon, A Comparative Analysis of Regional Correlation, Dynamic Time Warping, and Skeletal Tree Matching for Signature Verification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.7, p.710-717, July 1990 [doi>10.1109/34.56215]
• 29: Günter Rote, Computing the Fréchet distance between piecewise smooth curves, Computational Geometry: Theory and Applications, v.37 n.3, p.162-174, August, 2007 [doi>10.1016/j.comgeo.2005.01.004]
• 30: Y. Wang. Exact algorithm for partial curve matching via the fréchet distance. Technical Report OSUCISRC-9/08-TR48, The Ohio State University, 2008.
• 31: C. Wenk. Shape Matching in Higher Dimensions. PhD thesis, Dept. of Comput. Sci., Freie Univ. ersität, Berlin, 2002.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms