9 papers
A Strongly-Subquadratic -Approximation for the Fréchet Distance for Paths in Metric Spaces
Thijs van der Horst, Tim Ophelders
The Fréchet distance is a well-studied distance measure for paths in a metric space. It is mostly studied for paths in -dimensional Euclidean space. Here, computing the Fréche…
Reconfiguration of Squares Using a Constant Number of Moves Each
Thijs van der Horst, Maarten Löffler, Tim Ophelders +1
Multi-robot motion planning is a hard problem. We investigate restricted variants of the problem where square robots are allowed to slide over an arbitrary curve to a new position…
Computing the Fréchet Distance When Just One Curve is -Packed: A Simple Almost-Tight Algorithm
Jacobus Conradi, Ivor van der Hoog, Thijs van der Horst +1
We study approximating the continuous Fréchet distance of two curves with complexity and , under the assumption that only one of the two curves is -packed. Driemel, Har{…
Fréchet Distance in Unweighted Planar Graphs
Ivor van der Hoog, Thijs van der Horst, Eva Rotenberg +1
The Fréchet distance is a distance measure between trajectories in or walks in a graph . Given constant-time shortest path queries, the Discrete Fréchet distance $…
Faster, Deterministic and Space Efficient Subtrajectory Clustering
Ivor van der Hoog, Thijs van der Horst, Tim Ophelders
Given a trajectory and a distance , we wish to find a set of curves of complexity at most , such that we can cover with subcurves that each are within Fréche…
The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon
Thijs van der Horst, Marc van Kreveld, Tim Ophelders +1
The Fréchet distance is a popular similarity measure that is well-understood for polygonal curves in : near-quadratic time algorithms exist, and conditional lower bo…