Polyline Simplification using the Fréchet Distance - Algorithms and Engineering

Abstract

Polylines are used to represent curves by a sequence of straight segments. Simplification asks for a subsequence that is close to the original according to some similarity measure, and a given threshold value 𝜀. Polyline simplification is a building block for a variety of applications in computational geometry: drawing maps, or other vector graphics on various levels of detail, data compression, analysis of time series, robotics, bio-informatics and many more. A commonly used similarity measure is the Hausdorff distance that operates on point sets. In contrast, the Fréchet distance accounts for the course of a polyline. It is, therefore, considered to be more useful – but also more challenging in terms of computational complexity. Various applications and variations of the Fréchet distance have been studied over the last decades. In this work, we explore the use of the Fréchet distance for polyline simplification from four different angles. First of all, we present a new algorithm that significantly improves a long-standing running-time boundary of an existing algorithm. We explore theoretical aspects and we demonstrate its practical usefulness. Next, we propose two new variations on existing problem settings: we call them gradual simplification, and consistent simplification of polyline bundles. We believe these new problem settings to be interesting in their own. We analyze their characteristics, design efficient algorithms and, again, demonstrate their applicability. Lastly, we adapt an existing algorithm to a new application field, improving it in the process. We provide a new tool for the analysis of eye-tracking data, and, hopefully, more application fields. In addition to analyzing theoretical properties of algorithms, we always aim to prove the practical usefulness of our approaches. We recognize that oftentimes, deeper understanding of problems can not be gained from theoretical analysis alone. For this reason, we build prototypes implementing our new algorithms, and evaluate them on real-world data. The insights gained from these experiments help us in turn to improve the algorithmic designs.