Fréchet Distance for Uncertain Curves

DOI10.1145/3597640arXiv2004.11862OpenAlexW3018982745WikidataQ130980244 ScholiaQ130980244MaRDI QIDQ6051994FDOQ6051994

Authors:

Publication date: 23 October 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Abstract: In this paper we study a wide range of variants for computing the (discrete and continuous) Fr'echet distance between uncertain curves. We define an uncertain curve as a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fr'echet distance, which are the minimum and maximum Fr'echet distance for any realisations of the curves. We prove that both the upper and lower bound problems are NP-hard for the continuous Fr'echet distance in several uncertainty models, and that the upper bound problem remains hard for the discrete Fr'echet distance. In contrast, the lower bound (discrete and continuous) Fr'echet distance can be computed in polynomial time. Furthermore, we show that computing the expected discrete Fr'echet distance is #P-hard when the uncertainty regions are modelled as point sets or line segments. The construction also extends to show #P-hardness for computing the continuous Fr'echet distance when regions are modelled as point sets. On the positive side, we argue that in any constant dimension there is a FPTAS for the lower bound problem when $Delta/delta$ is polynomially bounded, where $delta$ is the Fr'echet distance and $Delta$ bounds the diameter of the regions. We then argue there is a near-linear-time 3-approximation for the decision problem when the regions are convex and roughly $delta$-separated. Finally, we also study the setting with Sakoe--Chiba time bands, where we restrict the alignment between the two curves, and give polynomial-time algorithms for upper bound and expected discrete and continuous Fr'echet distance for uncertainty regions modelled as point sets.

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

zbMATH Keywords

uncertaintyhardnesscurvesFréchet distance

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Dynamic programming algorithm optimization for spoken word recognition
• Title not available (Why is that?)
• Approximating \((k,\ell)\)-center clustering for curves
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• Computing the discrete Fréchet distance with imprecise input
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Approximating the Fréchet distance for realistic curves in near linear time
• Computing the Fréchet Gap Distance
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Distance measures for point sets and their computation
• Nearest-neighbor searching under uncertainty. II
• SMALLEST COLOR-SPANNING OBJECT REVISITED
• Preprocessing Imprecise Points and Splitting Triangulations
• The directed Hausdorff distance between imprecise point sets
• Removing local extrema from imprecise terrains
• Delaunay triangulation of imprecise points in linear time after preprocessing
• Nearest-neighbor searching under uncertainty. I
• On the Most Likely Convex Hull of Uncertain Points
• Geometric Computations on Indecisive Points
• Fréchet distance with speed limits
• Preprocessing imprecise points for Delaunay triangulation: simplified and extended
• Computing Visibility Information in an Inaccurate Simple Polygon
• Tight approximation bounds for connectivity with a color-spanning set
• Largest and Smallest Tours and Convex Hulls for Imprecise Points
• Title not available (Why is that?)
• Flow computations on imprecise terrains
• Four Soviets walk the dog: improved bounds for computing the Fréchet distance
• Unions of onions: preprocessing imprecise points for fast onion decomposition
• Selecting and covering colored points
• Computing the Fréchet distance with shortcuts is NP-hard
• Title not available (Why is that?)
• Fréchet distance under translation: conditional hardness and an algorithm via offline dynamic grid reachability
• SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
• Global Curve Simplification
• On optimal polyline simplification using the Hausdorff and Fréchet distance
• Fast Fréchet distance between curves with long edges
• Compact flow diagrams for state sequences
• Competitive query strategies for minimising the ply of the potential locations of moving points
• Computing the Fréchet distance between uncertain curves in one dimension
• Uncertain Curve Simplification

Cited In (1)

• Uncertain Curve Simplification

This page was built for publication: Fréchet Distance for Uncertain Curves

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