Computing the Fréchet Distance with a Retractable Leash

Article, Preprint, Report English OPEN
Buchin, K. ; Buchin, M. ; van Leusden, R. ; Meulemans, W. ; Mulzer, W. (2016)
  • Publisher: Springer Nature
  • Journal: Discrete & Computational Geometry
  • Related identifiers: doi: 10.1007/s00454-016-9800-8
  • Subject: Theoretical Computer Science | Geometry and Topology | Computational Theory and Mathematics | Computer Science - Computational Geometry | QA75 | Discrete Mathematics and Combinatorics

All known algorithms for the Fréchet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; second, they use this oracle to find the optimum from a finite set of critical values. We present a novel approach that avoids the detour through the decision version. This gives the first quadratic time algorithm for the Fréchet distance between polygonal curves in (Formula presented.) under polyhedral distance functions (e.g., (Formula presented.) and (Formula presented.)). We also get a (Formula presented.)-approximation of the Fréchet distance under the Euclidean metric, in quadratic time for any fixed (Formula presented.). For the exact Euclidean case, our framework currently yields an algorithm with running time (Formula presented.). However, we conjecture that it may eventually lead to a faster exact algorithm.
  • References (20)
    20 references, page 1 of 2

    1. Alt, H., Godau, M.: Computing the Fréchet distance between two polygonal curves. Int. J. Comput. Geom. Appl. 5(1-2), 78-99 (1995)

    2. Alt, H., Knauer, C., Wenk, C.: Matching polygonal curves with respect to the Fréchet distance. In: Proc. 18th Sympos. Theoret. Aspects Comput. Sci. (STACS), Dresden, pp. 63-74. Springer Berlin Heidelberg (2001)

    3. Brakatsoulas, S., Pfoser, D., Salas, R., Wenk, C.: On map-matching vehicle tracking data. In: Proc. 31st Int. Conf. on Very Large Data Bases (VLDB), pp. 853-864. VLDB Endowment (2005)

    4. Bringmann, K.: Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In: Proc. 55th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pp. 661-670. IEEE (2014)

    5. Bringmann, K., Mulzer, W.: Approximability of the discrete Fréchet distance. J. Comput. Geom. 7(2), 46-76 (2016)

    6. Brodal, G.S., Jacob, R.: Dynamic planar convex hull with optimal query time. In: Proc. 7th Scandinavian Workshop Algorithm Theory (SWAT), pp. 57-70. Springer Berlin Heidelberg (2000)

    7. Brodal, G.S., Jacob, R.: Dynamic planar convex hull. In: Proc. 43rd Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pp. 617-626. IEEE (2002)

    8. Buchin, K., Buchin, M., Gudmundsson, J.: Constrained free space diagrams: a tool for trajectory analysis. Int. J. GIS 24(7), 1101-1125 (2010)

    9. Buchin, K., Buchin, M., Gudmundsson, J., Löffler, M., Luo, J.: Detecting commuting patterns by clustering subtrajectories. Int. J. Comput. Geom. Appl. 21(3), 253-282 (2011)

    10. Buchin, K., Buchin, M., Meulemans, W., Mulzer, W.: Four Soviets walk the dog - with an application to Alt's conjecture. In: Proc. 25th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA), pp. 1399-1413. Society for Industrial and Applied Mathematics, Philadelphia, PA (2014)

  • Metrics
    No metrics available
Share - Bookmark