We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves $π$ and $σ$ of total complexity $n$ and a threshold $δ\geq 0$, we present an $\tilde{\mathcal{O}}(n^{7 + \frac{1}{3}})$ time algorithm to determine whether there exists a translation $t \in \mathbb{R}^2$ such that the Fréchet distance between $π$ and $σ+ t$ is at most $δ$. This improves on the previous best result, which is an $\mathcal{O}(n^8)$ time algorithm. We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class $\mathcal T$ of rationally parametrized transformations with $k$ degrees of freedom, we show that one can determine whether there is a transformation $τ\in \mathcal T$ such that the Fréchet distance between $π$ and $τ(σ)$ is at most $δ$ in $\tilde{\mathcal{O}}(n^{3k+\frac{4}{3}})$ time.

We consider the problem of computing an approximate weighted shortest path in a weighted planar subdivision, with weights assigned from the set {0, 1, ∞}. The subdivision includes zero-cost regions (0-regions) with weight 0 and obstacles with weight ∞, all embedded in a plane with weight 1. In a polygonal domain, where the 0-regions and obstacles are non-overlapping polygons (not necessarily convex) with in total N vertices, we present an algorithm that computes a (1 + ε)-approximate spanner of the input vertices in expected Oe(N/ε3) time1, for 0 < ε < 1. Using our spanner, we can compute a (1 + ε)-approximate weighted shortest path between any two points (not necessarily vertices) in Oe(N/ε3) time. Furthermore, we prove that our results more generally apply to non-polygonal convex regions. Using this generalisation, one can approximate the weak partial Fréchet similarity [7] between two polygonal curves in expected Oe(n2/ε2) time, where n is the total number of vertices of the input curves.

We present a near-linear time approximation algorithm for the subtrajectory cluster problem of c-packed trajectories. Given a trajectory T of complexity n, an approximation factor ε, and a desired distance d, the problem involves finding m subtrajectories of T such that their pair-wise Fréchet distance is at most (1 + ε)d. At least one subtrajectory must be of length l or longer. A trajectory T is c-packed if the intersection of T and any ball B with radius r is at most c · r in length. Previous results by Gudmundsson and Wong [24] established an Ω(n3) lower bound unless the Strong Exponential Time Hypothesis fails, and they presented an O(n3 log2 n) time algorithm. We circumvent this conditional lower bound by studying subtrajectory cluster on c-packed trajectories, resulting in an algorithm with an O((c2n/ε2) log(c/ε) log(n/ε)) time complexity.