Overview
Frechet distance compares two curves by asking how closely they can be traversed from start to end without moving backward along either curve.
CoreSource checked
Frechet Distance
Measures curve similarity while preserving the order of points along each curve.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Intermediate
- Family
- Shape Similarity
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 7
- Code example
- Ready
- Visualization
- Ready
Core Concepts
curve distanceshape similaritygeometry
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use when path or curve similarity should respect traversal order.
- Use when Hausdorff distance is too permissive because it ignores ordering.
When Not to Use
- Avoid when point-set proximity without ordering is the intended comparison.
- Avoid when noisy sampling requires preprocessing or simplification first.
What It Does
- Frechet Distance uses tracking the minimum leash length needed to traverse two curves in order for curve distance
- Organizes the work around curve distance and shape similarity.
Use Cases
- Production and research workloads requiring shape similarity via asking how closely they can be traversed from start to end without moving backward along either curve.
- Shape Similarity pipelines where O(n log n) time and O(n) space fit system constraints.
- Engineering comparisons against Voronoi-Based Medial Axis and Hausdorff Distance when tuning shape similarity.
Inputs
- Points, segments, polygons, or geometric primitives
- Query or construction parameters
Outputs
- Geometric decision, measurement, or constructed structure
Key Formulas (1)
Discrete Frechet recurrence
ca(i,j) = max(d(Pi,Qj), min(ca(i−1,j), ca(i−1,j−1), ca(i,j−1)))
ca(i,j) = max(d(P_i,Q_j), min(ca(i-1,j), ca(i-1,j-1), ca(i,j-1)))Tracks the best leash length for prefixes of two curves.
Pseudocode
- 1.Choose discrete or continuous Frechet variant
- 2.Compute point distances or free-space intervals
- 3.Propagate reachable states in traversal order
- 4.Track the smallest leash length that permits a full traversal
- 5.Return the resulting distance
Canonical Example
- Input
- curves A: (0,0)->(1,0) and B: (0,0)->(1,1)
- Output
- distance 1 for the discrete endpoint comparison
- Explanation
- The largest matched point distance along the ordered traversal is 1.
Implementation Notes
- State whether the discrete or continuous Frechet distance is used.
- Use Euclidean point distance consistently.
- Test identical curves, reversed curves, and curves with a single outlier.
Common Pitfalls
- Frechet distance is sensitive to curve parameterization and sampling.
- Reversing one curve changes the result unless reversal is considered separately.
- Discrete and continuous variants have different algorithms and interpretations.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow tracking the minimum leash length needed to traverse two curves in order on a small curve distance example.
Step 1 of 5: Choose discrete or continuous Frechet variant
geometry-mechanismNotes
Frechet distance is order-aware; it answers a different question from unordered point-set distances.
Sources (2)
What each reference supports for this entry.
Computational Geometry: Algorithms and Applications
BookTextbook support for Frechet Distance's computational geometry problem family, predicates, structures, or geometric construction.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Frechet Distance in the computational geometry benchmark area.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toHausdorff Distance
Geometry · Core
Both address curve distance, but they make different modeling or performance tradeoffs.
Compare with thisAlternativesProcrustes Analysis
Geometry · Core
Procrustes Analysis and Frechet Distance solve related shape alignment problems with different assumptions and tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toVoronoi-Based Medial Axis
Both address curve distance, but they make different modeling or performance tradeoffs.
Alternative toHausdorff Distance
Both address curve distance, but they make different modeling or performance tradeoffs.
Alternative toShape Context Matching
Both address curve distance, but they make different modeling or performance tradeoffs.
Related Algorithms
Tags
GeometryComputational Geometry