Fast Frechet Distance Between Curves With Long Edges

2017/10/28 by Gudmundsson, Joachim, Mirzanezhad, Majid, Mohades, Ali +1 · 1 citation
#Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1710.10521

Abstract

Computing the Fréchet distance between two polygonal curves takes roughly quadratic time. In this paper, we show that for a special class of curves the Fréchet distance computations become easier. Let P and Q be two polygonal curves in ℝ^d with n and m vertices, respectively. We prove four results for the case when all edges of both curves are long compared to the Fréchet distance between them: (1) a linear-time algorithm for deciding the Fréchet distance between two curves, (2) an algorithm that computes the Fréchet distance in O((n+m)log (n+m)) time, (3) a linear-time √(d)-approximation algorithm, and (4) a data structure that supports O(mlog² n)-time decision queries, where m is the number of vertices of the query curve and n the number of vertices of the preprocessed curve.

Cited by

• Computing the Fréchet Distance When Just One Curve is c-Packed: A Simple Almost-Tight Algorithm

Related

• Fréchet Distance in Subquadratic Time
• Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts
• On Computing the k-Shortcut Fréchet Distance
• Faster Fréchet Distance Approximation through Truncated Smoothing
• Faster Fréchet distance approximation through truncated smoothing