The following list is a selection of the Master's theses, supervised by members of the AGA group.

Efficiently answering Fréchet queries (PDF)

Supervisors:
Kevin Buchin
and
Wouter Meulemans

With the recent rise of sensor-sourced positioning data, the need to derive meaningful conclusions from trajectory data increases. A prominent trajectory comparison metric, the Fréchet distance, is often used but is inefficent to compute for large input sets. This thesis attempts to improve the efficiency of Fréchet related computations for representative problems, with representative data. This thesis presents novel efficiency-focused adaptations to existing Fréchet algorithms and their composition into an efficient pruning-based query answering algorithm. The investigated approaches can be integrated piecemeal into other computation systems, and the thesis examines when and how which approach is most effective. The algorithms proposed in this thesis have been shown to be successful in practice, reaching second place in the ACM SIGSPATIAL GIScup of 2017.

This thesis resulted in the following
publication:

Efficient Trajectory Queries Under the Fréchet Distance (GIS Cup)

Visualization for text-based research in philosophy (PDF)

Supervisors:
Michel Westenberg
,
Thom Castermans
and
Rob Koopman

Conceptual analysis and close reading form an important part of philosophy research. A researcher focuses on an individual text passage from a collection of works to analyse its full interpretation. This can be a very time-consuming process if this is done manually since it is often also involved with complex work that have a high conceptual density. The analysis can lead to the generation of hypotheses based on contradicting text passage interpretations. This thesis introduces BolVis, an interactive visualization tool for text-based research in philosophy that can be used to accept or reject these hypotheses. We designed and implemented a prototype that uses semantic similarity search on individual words, phrases and sentences. The visualization allows investigators to quickly discover the most relevant parts of the corpus corresponding to their search query and provides functionalities that makes the exploration of the semantic context easier. We apply our tool to a corpus containing the works of polymath Bernard Bolzano (1781-1848) consisting of around 11,000 pages to show the benefits of BolVis.

This thesis resulted in the following
publication:

BolVis: Visualization for Text-Based Research in Philosophy

Stability of treemap algorithms (PDF)

Supervisors:
Bettina Speckmann
and
Kevin Verbeek

To evaluate the quality of a treemap algorithm, two quality metrics should be considered. The first quality metric is the aspect ratio of the treemaps generated by the algorithm. The aspect ratio determines how accurate the areas of the rectangles in the treemap can be interpreted by the user. The second quality metric, which is the main focus of this thesis, is the stability score. The stability score indicates how hard it is to track rectangles when the treemap has changed. The aim of this thesis is twofold. The first aim is to evaluate how the stability score can be objectively determined. The second aim is to develop a treemap algorithm that is able to generate treemap that have both low stability scores and low aspect ratios. To objectively determine stability score we first evaluated the existing definitions of stability. We noticed that none of the current definitions take the structures in the treemap into account. We then developed a new definition for the stability score, that does take these structure into account. The new definition is based on the change in the relative positions of the rectangles with regard to each other. To develop new treemap algorithms that are able to generate treemaps that have both a low stability score and a good aspect ratio, we introduced the concept of local moves.Local moves manipulate an existing layout in such a way that the resulting layout onlydiffers slightly compared to the original layout. Using a sequence of local moves, it is moreover possible to manipulate the layout such that it is possible to reach any layout from any layout. We developed two new treemap algorithms using these local moves. The newly developed algorithm are the first treemap algorithm that can generate non-sliceable treemaps. In terms of the stability score, the newly developed algorithm out-perform all current practical treemap algorithms on both artificial and real world dataset. Moreover the newly developed algorithms perform well on the aspect ratio quality measure as well.

This thesis resulted in the following
publication:

Stable Treemaps Via Local Moves

Lower bounds for preprocessing algorithms based on protrusion replacement (PDF)

Supervisor:
Bart Jansen

In general, a kernelization algorithm is an efficient preprocessing procedure that reduces the size of the input to a difficult computational problem, without changing the answer. For optimization problems, we know how much the size of an optimum solution changes by reducing the size of the input using a kernelization algorithm. Garnero et al. recently proposed a new kind of kernelization algorithm for optimization problems on planar graphs: The algorithm reduces a subgraph $H$ of planar graph $G$, to a different subgraph $H′$ called a *representative*. Subgraphs $H$ and $H′$ are connected to the remainder of $G$ by $t$ vertices. This reduction is done for multiple of such subgraphs in $G$, that are also connected to the remainder of $G$ by $t$ vertices.

The size of an optimum solution after reducing $H$ to $H′$, can be inferred by only looking at subgraph $H$ and the representative $H′$: We say that subgraph $H$ is equivalent to representative $H′$ if there is a constant $c$, such that the optimum solution of every graph $G$, that has $H$ as a subgraph,changes by exactly $c$, by replacing $H$ by $H′$. Therefore, the proposed kernelization algorithm reduces a subgraph $H$ of $G$ to an equivalent representative $H′$. For the kernelization algorithm to be fast, one should be able to efficiently find a representative $H′$ that is equivalent to a subgraph $H$ in $G$. This is possible if subgraph $H$ has bounded treewidth or bounded pathwidth.

Let $R_t$ be a set of these subgraphs called representatives. Garnero et al. showed that an upper bound on the size of representatives in $R_t$ is doubly-exponentially dependent on $t$, the number of vertices with which these subgraphs are connected to the remainder of a graph. We propose lower bounds for the size of these representatives, also dependent on $t$.

We give a lower bound of $\Omega(2t/\sqrt{4t})$ on the number of vertices of a representative in such a set $R_t$ for Independent Set. This bound holds for sets of planar representatives with bounded treewidth/pathwidth. We also show that the equivalence relation that we explained before has at least $2^{2^t}/\sqrt{4t}$ equivalence classes for Independent Set on general graphs. Furthermore, we improve on the results of Garnero et al. by giving an upper bound of $2^{2^t-1}$ on the number of equivalence classes for Independent Set on general graphs. These bounds even hold for the number of equivalence classes for planar subgraphs of bounded treewidth/pathwidth.

The size of an optimum solution after reducing $H$ to $H′$, can be inferred by only looking at subgraph $H$ and the representative $H′$: We say that subgraph $H$ is equivalent to representative $H′$ if there is a constant $c$, such that the optimum solution of every graph $G$, that has $H$ as a subgraph,changes by exactly $c$, by replacing $H$ by $H′$. Therefore, the proposed kernelization algorithm reduces a subgraph $H$ of $G$ to an equivalent representative $H′$. For the kernelization algorithm to be fast, one should be able to efficiently find a representative $H′$ that is equivalent to a subgraph $H$ in $G$. This is possible if subgraph $H$ has bounded treewidth or bounded pathwidth.

Let $R_t$ be a set of these subgraphs called representatives. Garnero et al. showed that an upper bound on the size of representatives in $R_t$ is doubly-exponentially dependent on $t$, the number of vertices with which these subgraphs are connected to the remainder of a graph. We propose lower bounds for the size of these representatives, also dependent on $t$.

We give a lower bound of $\Omega(2t/\sqrt{4t})$ on the number of vertices of a representative in such a set $R_t$ for Independent Set. This bound holds for sets of planar representatives with bounded treewidth/pathwidth. We also show that the equivalence relation that we explained before has at least $2^{2^t}/\sqrt{4t}$ equivalence classes for Independent Set on general graphs. Furthermore, we improve on the results of Garnero et al. by giving an upper bound of $2^{2^t-1}$ on the number of equivalence classes for Independent Set on general graphs. These bounds even hold for the number of equivalence classes for planar subgraphs of bounded treewidth/pathwidth.

This thesis resulted in the following
publications:

Lower Bounds for Protrusion Replacement by Counting Equivalence Classes

Lower Bounds for Protrusion Replacement by Counting Equivalence Classes

GlottoVis: Visualizing the Descriptive and Endangerment Status of Languages (PDF)

Supervisors:
Bettina Speckmann
and
Kevin Verbeek

This thesis discusses the design and implementation of an interactive visualization of the Glottolog database. This visualization is web-based and shows glyphs, representing languages, on an interactive map. An algorithm ensures that glyphs never overlap, but instead are merged when they would.

This thesis resulted in the following
publications:

GlottoVis: Visualizing Language Endangerment and Documentation

Simultaneous Visualization of Language Endangerment and Language Description

Algorithms for comparing moving complex shapes: higher-dimensional Fréchet distance (PDF)

Supervisors:
Kevin Buchin
and
Bettina Speckmann

We investigate methods for the computation of the similarity between moving shapes. We will focus on the comparison of moving curves, which are modeled as moving polylines. Moving polylines are in turn represented as quadrilateral meshes. We present methods for the comparison of such quadrilateral meshes under adaptations of the Fréchet distance. Our results show that computing the Fréchet distance between quadrilateral meshes is NP-hard even in various settings. We also consider three more restricted settings in which the Fréchet distance can be computed using polynomial time algorithms. The polynomial algorithms assume that the compared moving shapes move synchronously, such that part of their matching is known in advance.

This thesis resulted in the following
publications:

Computing the Similarity Between Moving Curves

Computing the Similarity Between Moving Curves

Edge bundling and routing via well-separated pair decomposition and visiblity spanners (PDF)

Supervisor:
Bettina Speckmann

We present a novel edge bundling algorithm which defines its bundles based on a well-separated pair decomposition and routes bundles individually on a sparse visibility spanner. We prove that the bundles induced by the well-separated pair decomposition consist of compatible edges according to the measures by Holten and Van Wijk. The greedy sparsification of the visibility graph allows us to easily route around obstacles and guarantees a bound on the detour of the shortest paths between vertices. Our experimental results are visually appealing and convey a sense of abstraction and order. Edge clutter is significantly reduced while the individual routing of the bundles retains nearly all connectivity information.

This thesis resulted in the following
publication:

Clustered Edge Routing