Four Soviets walk the dog: improved bounds for computing the Fréchet distance

DOI10.1007/S00454-017-9878-7zbMATH Open1379.68319arXiv1209.4403OpenAlexW2588820692WikidataQ59528497 ScholiaQ59528497MaRDI QIDQ2408191FDOQ2408191

Authors: Kevin Buchin, Maike Buchin, Wouter Meulemans, Wolfgang Mulzer 

Publication date: 10 October 2017

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: Given two polygonal curves in the plane, there are many ways to define a notion of similarity between them. One popular measure is the Fr'echet distance. Since it was proposed by Alt and Godau in 1992, many variants and extensions have been studied. Nonetheless, even more than 20 years later, the original $O(n^{2}logn)$ algorithm by Alt and Godau for computing the Fr'echet distance remains the state of the art (here, $n$ denotes the number of edges on each curve). This has led Helmut Alt to conjecture that the associated decision problem is 3SUM-hard. In recent work, Agarwal et al. show how to break the quadratic barrier for the discrete version of the Fr'echet distance, where one considers sequences of points instead of polygonal curves. Building on their work, we give a randomized algorithm to compute the Fr'echet distance between two polygonal curves in time $O(n^{2}sqrtlogn(loglogn{)}^{3/2})$ on a pointer machine and in time $O(n^2(loglogn{)}^2)$ on a word RAM. Furthermore, we show that there exists an algebraic decision tree for the decision problem of depth $O(n^{2-varepsilon})$, for some $varepsilon>0$. We believe that this reveals an intriguing new aspect of this well-studied problem. Finally, we show how to obtain the first subquadratic algorithm for computing the weak Fr'echet distance on a word RAM.

Full work available at URL: https://arxiv.org/abs/1209.4403

Recommendations

• Four Soviets walk the dog -- with an application to Alt's conjecture
• Computing the Fréchet distance with a retractable leash
• Computing the Fréchet distance with a retractable leash

zbMATH Keywords

pointer machineword RAMalgebraic decision treefour Russian trickFréchet distance

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Computational Complexity
• On a class of \(O(n^ 2)\) problems in computational geometry
• Subquadratic algorithms for 3SUM
• Towards polynomial lower bounds for dynamic problems
• Title not available (Why is that?)
• Efficiency of a Good But Not Linear Set Union Algorithm
• Title not available (Why is that?)
• Title not available (Why is that?)
• Threesomes, degenerates, and love triangles
• Lower bounds for linear degeneracy testing
• On range searching with semialgebraic sets. II.
• Parity, circuits, and the polynomial-time hierarchy
• Title not available (Why is that?)
• Surpassing the information theoretic bound with fusion trees
• Storage Modification Machines
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Approximability of the discrete Fréchet distance
• Detecting commuting patterns by clustering subtrajectories
• Computing the Fréchet distance with a retractable leash
• Geodesic Fréchet distance inside a simple polygon
• Approximating the Fréchet distance for realistic curves in near linear time
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Comparison of distance measures for planar curves
• Computing the Fréchet distance between simple polygons
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• The Computational Geometry of Comparing Shapes
• Fréchet Distance for Curves, Revisited
• Near-linear time approximation algorithms for curve simplification
• New similarity measures between polylines with applications to morphing and polygon sweeping
• Delaunay triangulations in O (sort( n )) time and more
• Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• How good is the information theory bound in sorting?
• Necklaces, convolutions, and \(X+Y\)
• On a circle placement problem
• Computing connected components on parallel computers
• Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
• Fréchet distance with speed limits
• A MATHEMATICAL THEORY OF ADAPTIVE CONTROL PROCESSES
• Title not available (Why is that?)
• Improved parallel integer sorting without concurrent writing
• Fast Fréchet queries
• An Expander-Based Approach to Geometric Optimization
• Approximate nearest neighbor algorithms for Frechet distance via product metrics
• Can we compute the similarity between surfaces?
• Fréchet distance of surfaces: some simple hard cases
• Computing the Fréchet distance between folded polygons
• Title not available (Why is that?)
• The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
• Improved algorithms for partial curve matching

Cited In (17)

• Title not available (Why is that?)
• Approximability of the discrete Fréchet distance
• Approximating the packedness of polygonal curves
• When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
• \((1+\varepsilon)\)-ANN data structure for curves via subspaces of bounded doubling dimension
• Walking your dog in the woods in polynomial time
• Translation invariant Fréchet distance queries
• Fréchet Distance for Uncertain Curves
• Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
• Fast Fréchet distance between curves with long edges
• Computing the Fréchet distance between uncertain curves in one dimension
• Fréchet distance between two point sets
• Computing the Fréchet distance between uncertain curves in one dimension
• Computing the Fréchet distance with a retractable leash
• Four Soviets walk the dog -- with an application to Alt's conjecture
• Walking the dog fast in practice: algorithm engineering of the Fréchet distance
• Approximating the Packedness of Polygonal Curves

This page was built for publication: Four Soviets walk the dog: improved bounds for computing the Fréchet distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2408191)