Projects

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.

Data visualization, the main topic of this dissertation, is the science concerned with the design and creation of visual representations intended to convey information and facilitate understanding. In a scientific context, the data to be visualized are typically research results, which can originate from any discipline. The main challenges in data visualization are to find visual representations which (1) are as accurate as possible, (2) can be understood quickly and well by viewers, and (3) can be produced automatically and efficiently. The latter is especially important when large or dynamic data sets are involved. This dissertation is focused on addressing these challenges for a particular application domain: the visualization of archaeological data. We identify general properties that often characterize archaeological data and discuss a variety of visualization methods suitable for data with these properties. For existing methods from the area of mathematics and computer science, we explain how they can be applied – either directly or with some adaptations – in the context of archaeology. We also introduce new approaches, tailored to various archaeological applications. Case studies and real archaeological data sets are used to demonstrate the use of these approaches in practical applications. However, because of our focus on general data properties rather than specific data sets, the methods presented in this dissertation are in fact widely applicable beyond the field of archaeology as well.