6 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échet…
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échet…
Faster Fréchet Distance Approximation through Truncated Smoothing
Thijs van der Horst, Marc van Kreveld, Tim Ophelders +1
The Fréchet distance is a commonly used distance measure for curves. Computing the Fréchet distance between two polygonal curves of vertices takes roughly quadratic time, and c…
Robust Bichromatic Classification using Two Lines
Erwin Glazenburg, Thijs van der Horst, Tom Peters +2
Given two sets and of points in the plane, we present efficient algorithms to find a two-line linear classifier that best separates the "red" points in from the "bl…
Simply Realising an Imprecise Polyline is NP-hard
Thijs van der Horst, Tim Ophelders, Bart van der Steenhoven
We consider the problem of deciding, given a sequence of regions, if there is a choice of points, one for each region, such that the induced polyline is simple or weakly simple, me…
A Subquadratic -approximation for the Continuous Fréchet Distance
Thijs van der Horst, Marc van Kreveld, Tim Ophelders +1
The Fréchet distance is a commonly used similarity measure between curves. It is known how to compute the continuous Fréchet distance between two polylines with and vertice…