The fréchet distance revisited and extended

Given two simplicial complexes in Rd and start and end vertices in each complex, we show how to compute curves (in each complex) between these vertices, such that the weak Fréchet distance between these curves is minimized. As a polygonal curve is a complex, this generalizes the regular notion of weak Fréchet distance between curves. We also generalize the algorithm to handle an input of k simplicial complexes. Using this new algorithm, we can solve a slew of new problems, from computing a mean curve for a given collection of curves to various motion planning problems. Additionally, we show that for the mean curve problem, when the k input curves are c-packed, one can (1+ϵ-approximate the mean curve in near-linear time, for fixed k and ϵ. Additionally, we present an algorithm for computing the strong Fréchet distance between two curves, which is simpler than previous algorithms and avoids using parametric search.

• Publication year

  2012

• Venue

  TALG

• Publication date

  2012-02-24

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2532646arXiv 1202.5610
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Aligning Two Convex Figures to Minimize Area or Perimeter

  2012influential reference
• Improved Algorithms for Partial Curve Matching

  2011cited by this paper
• The frechet distance revisited and extended

  2011cited by this paper
• Fréchet Distance of Surfaces: Some Simple Hard Cases

  2010cited by this paper
• Median Trajectories

  2010cited by this paper
• Approximating the Fréchet Distance for Realistic Curves in Near Linear Time

  2010cited by this paper
• Detecting Commuting Patterns by Clustering Subtrajectories

  2008cited by this paper
• Geodesic Fréchet distance inside a simple polygon

  2008cited by this paper
• Detecting single file movement

  2008cited by this paper
• Can We Compute the Similarity between Surfaces?

  2007cited by this paper
• Fréchet Distance Based Approach for Searching Online Handwritten Documents

  2007cited by this paper
• How Difficult is it to Walk the Dog ?

  2007cited by this paper
• Addressing the Need for Map-Matching Speed: Localizing Global Curve-Matching Algorithms

  2006influential reference
• On Map-Matching Vehicle Tracking Data

  2005influential reference
• Optimization of subsequence matching under time warping in time-series databases

  2005cited by this paper
• On the Fréchet distance of a set of curves

  2004influential reference
• Matching planar maps

  2003cited by this paper
• Parametric search made practical

  2002cited by this paper
• Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification

  1999cited by this paper
• On the complexity of measuring the similarity between geometric objects in higher dimensions

  1999cited by this paper
• Scaling up Dynamic Time Warping to Massive Dataset

  1999cited by this paper
• Parallel Genetic-Based Hybrid Pattern Matching Algorithm for Isolated Word Recognition

  1998cited by this paper
• Computing the Fréchet distance between two polygonal curves

  1995influential reference
• Randomized algorithms

  1995cited by this paper
• Randomized Optimal Algorithm for Slope Selection

  1991cited by this paper

• On computing the (exact) Fréchet distance with a frog

  2025cites this paper
• Optimising quality in time-variant systems: a focus on dynamics and heterogeneity

  2025cites this paper
• Transforming Dogs on the Line: On the Fréchet Distance Under Translation or Scaling in 1D

  2025influential citation
• Comparative analysis and evaluation of ageing forecasting methods for semiconductor devices in online health monitoring

  2025cites this paper
• A WSPD, Separator and Small Tree Cover for c-packed Graphs

  2025cites this paper
• A Multi-Objective Genetic Algorithm for Retrieving the Parameters of Sweet Pepper (Capsicum annuum) from the Diffuse Spectral Response

  2025cites this paper
• AdaptNet: Rethinking Sensing and Communication for a Seamless Internet of Drones Experience

  2024cites this paper
• Artificial Intelligence-Based, Wavelet-Aided Prediction of Long-Term Outdoor Performance of Perovskite Solar Cells

  2024cites this paper
• Fréchet Edit Distance

  2024influential citation
• FFAD: A Novel Metric for Assessing Generated Time Series Data Utilizing Fourier Transform and Auto-encoder

  2024cites this paper
• Predicting Generalization of AI Colonoscopy Models to Unseen Data

  2024cites this paper
• Advancing Generative Model Evaluation: A Novel Algorithm for Realistic Image Synthesis and Comparison in OCR System

  2024cites this paper
• Predicting the generalization of computer aided detection (CADe) models for colonoscopy

  2024cites this paper
• ACbot: an IIoT platform for industrial robots

  2024cites this paper
• Approximating the Fréchet distance when only one curve is c-packed

  2024cites this paper
• ORION: Verification of drone trajectories via remote identification messages

  2024cites this paper
• On the Budgeted Hausdorff Distance Problem

  2023cites this paper
• Computational Geometry: Theory and Applications

  2023cites this paper
• AI-Driven Identification of Contrail Sources: Integrating Satellite Observation and Air Traffic Data

  2023cites this paper
• Global optimisation matching method for multi-representation buildings constrained by road network

  2023cites this paper
• Health Indicator Similarity Analysis-Based Adaptive Degradation Trend Detection for Bearing Time-to-Failure Prediction

  2023cites this paper
• Ice monitoring of aluminum conductor steel-reinforced cables using guided waves

  2023cites this paper
• Computing the Fréchet Distance Between Uncertain Curves in One Dimension

  2021cites this paper
• Obstacle Avoidance Methods Based on Geometric Information Under the DMPs Framework

  2021cites this paper
• Streaming Algorithm to the Decomposition of a Polyatomic Molecules Mass Spectra on the Polychlorinated Biphenyls Molecule Example

  2021cites this paper
• Fast and Exact Convex Hull Simplification

  2021cites this paper
• Parameter Selection Criteria for Tomo-SAR Focusing

  2021cites this paper
• Approximating The p-Mean Curve of Large Data-Sets

  2020cites this paper
• Sampling and sparsification for approximating the packedness of trajectories and detecting gatherings

  2020cites this paper
• Computing the Fréchet Gap Distance

  2020influential citation
• Middle curves based on discrete Fréchet distance

  2020influential citation
• Statistical Regularization for Enhanced TomoSAR Imaging

  2020cites this paper
• Fréchet Distance for Uncertain Curves

  2020cites this paper
• A Hybrid Prognostics Approach for Estimating Remaining Useful Life of Rolling Element Bearings

  2020cites this paper
• Approximating p-Mean Curve of Large Data-Sets

  2020cites this paper
• Convex Frechet Distance in Specific Emitter Identification

  2020cites this paper
• Computing the Exact Packedness of a Curve

  2020cites this paper
• Approximating the packedness of polygonal curves

  2020cites this paper
• On the complexity of the middle curve problem

  2020cites this paper
• Analysis of the Response of Modal Parameters to Damage in CFRP Laminates Using a Novel Modal Identification Method

  2019cites this paper
• Weighted Minimum Backward Frechet Distance

  2019cites this paper
• TraV: An Interactive Exploration System for Massive Trajectory Data

  2019cites this paper
• Fuzzy Logic Type-2 Based Wireless Indoor Localization System for Navigation of Visually Impaired People in Buildings

  2019cites this paper
• Rock Climber Distance: Frogs versus Dogs

  2019cites this paper
• NSF Proposal: AF 7435149: Towards better geometric algorithms: Summarizing, partitioning and shrinking data

  2018cites this paper
• Map-matching using shortest paths

  2018cites this paper
• SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension

  2018cites this paper
• Iterative Availability Assessment Approach for Multi-Feeder Industrial Energy System Sections

  2018cites this paper
• Iterative Availability Assessment Approach for Multi-Feeder Industrial Energy System Sections

  2018cites this paper
• Path Planning for Within-Hand Manipulation over Learned Representations of Safe States

  2018cites this paper
• Following Surgical Trajectories with Concentric Tube Robots via Nearest-Neighbor Graphs

  2018cites this paper
• Minimizing the Fréchet Error of Task-Space Paths for Manipulators and Surgical Robots

  2018cites this paper
• Minimizing Task-Space Fréchet Error via Efficient Incremental Graph Search

  2017influential citation
• Four Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance

  2017influential citation
• 1 Following Paths in Task Space : Distance Metrics and Planning Algorithms

  2017influential citation
• Fréchet distance: How to walk your dog

  2017influential citation
• Bimanual Word Gesture Keyboards for Mid-air Gestures

  2017cites this paper
• Local frechet distance in specific emitter identification

  2017cites this paper
• Applying the frechet distance to the specific emitter identification

  2016cites this paper
• Average curve of n smooth planar curves

  2016cites this paper
• Sampling-Based Bottleneck Pathfinding with Applications to Fréchet Matching

  2016influential citation
• Tight(er) bounds for similarity measures, smoothed approximation and broadcasting

  2016cites this paper
• On Computing the Fréchet Distance Between Surfaces

  2016cites this paper
• Efficient sampling-based bottleneck pathfinding over cost maps

  2016cites this paper
• Discrete Geometric Path Analysis in Computational Geometry

  2016cites this paper
• A Segmented Template Optimization Using the Frechet Distance

  2016cites this paper
• A Middle Curve Based on Discrete Fréchet Distance

  2016influential citation
• 2 Computing the Similarity Between Moving Curves

  2015cites this paper
• 1 Sampling from Discrete Distributions

  2015cites this paper
• Sampling from Discrete Distributions and Computing Frechet Distances

  2015cites this paper
• Geometric Algorithms for Trajectory Analysis

  2015cites this paper
• Trajectory Box Plot; a New Pattern to Summarize Movements

  2015cites this paper
• Clustering time series under the Fréchet distance

  2015cites this paper
• Young Reseachers Forum: Book of Abstracts

  2015influential citation
• Computing the Similarity Between Moving Curves

  2015cites this paper
• Central Trajectories

  2015cites this paper
• Path Similarity Analysis: A Method for Quantifying Macromolecular Pathways

  2015cites this paper
• Similarity measures and algorithms for cartographic schematization

  2014influential citation
• Algorithms for comparing moving complex shapes:higher-dimensional Fréchet distance

  2014cites this paper
• Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails

  2014cites this paper
• Realistic Analysis for Algorithmic Problems on Geographical Data

  2013cites this paper
• Simple Curve Embedding

  2013influential citation
• Computing the Fréchet Distance with a Retractable Leash

  2013cites this paper
• Applied Similarity Problems Using Frechet Distance

  2013cites this paper
• Net and prune: a linear time algorithm for euclidean distance problems

  2013cites this paper
• Measuring similarity between curves on 2-manifolds via homotopy area

  2013cites this paper
• AngryAnts: A Citizen Science Approach to Computing Accurate Average Trajectories

  2012cites this paper
• Four Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance

  2012influential citation
• How to Walk Your Dog in the Mountains with No Magic Leash

  2012cites this paper
• Four Soviets Walk the Dog - with an Application to Alt's Conjecture

  2012influential citation
• Computing the Discrete Fréchet Distance in Subquadratic Time

  2012cites this paper
• Locally Correct Frechet Matchings

  2012cites this paper
• Jaywalking Your Dog: Computing the Fréchet Distance with Shortcuts

  2011cites this paper
• Improved Algorithms for Partial Curve Matching

  2011cites this paper