(cum laude: ranked among the top 5% at TU/e)
Algorithms for Visualization in Digital Humanities (PDF
This dissertation encompasses the most important results of the interdisciplinary research project CatVis, which is a collaborative effort between computer scientists, data scientists, and philosophers. We describe a number of methodological and philosophical challenges that arose within CatVis. After that we present GlamMap, a visualization tool for large, multi-variate georeferenced Humanities data sets. Inspired by GlamMap, we present a fully dynamic kinetic data structure that maintains a set of $n$ disjoint growing squares. This leads to an $O(n\,\alpha(n) \log^5 n)$ time algorithm to solve the agglomerative clustering problem. Although our algorithm is asymptotically much faster than previous approaches, from a practical point of view, it does not perform better for $n \leq 10^6$. We present a new agglomerative clustering algorithm which works efficiently in practice. Other results contained in the dissertation are a novel type of low distortion radial embedding and a study of plane supports of hypergraphs.
Algorithms for River Network Analysis (PDF
Braided rivers and estuaries are examples of river networks: systems consisting of intertwined channels and islands, that can behave in complex and unpredictable ways. The study of river networks is important because they play a crucial part in the natural environment. Therefore, river networks form one of the key research interests in geomorphology, but so far their analysis has been carried out mostly by hand. In this thesis, we take an algorithmic approach to the study of river networks. We employ techniques from topology on a digital elevation model of the river to automatically construct a graph representing significantly different channels of water in the river network, and we apply this method to the analysis of two real-world rivers. Furthermore, we study methods to track the evolution of river network over time, and a method to create more compact visualizations of a network.
Continuous Similarity Measures for Curves and Surfaces (PDF
IPA Dissertation Award 2018
Distinguishing objects is a crucial task for survival. Animals survive by distinguishing predators from prey, and poisonous plants from edible ones. As such, objects come in different types, and to recognize the type of an object, one needs a description of it. In theory, one would best describe it by listing all objects of that type. However, there tend to be many objects of a given type, and sometimes, objects of the same type may not have been discovered. A more practical way to describe a type would be to provide a collection of objects of that type, complemented by a collection of objects not of that type. For an object of a given type, we expect that it is similar to the objects of the same type, and dissimilar from other objects. To test whether an object is of a given type, one can compare it to other objects that do and do not fit the description of that type. The similarity of objects can be measured in many different ways, and different applications tend to have different similarity measures that are suitable. In this thesis, we investigate computational aspects of various similarity measures between curves, as well as surfaces.
Geographic Graph Construction and Visualization (PDF
A geographic graph is a way to represent information about the network of connections between geographic locations. As our small world has grown ever more interconnected, it has become an important way to represent data from a wide variety of sources. In this thesis we consider methods for the efficient construction of a geographic graph from a set of locations. The graphs created by our algorithms are constructed to have various useful properties and applications to real world problems. Furthermore, we propose and evaluate methods to visualize existing geographic graphs. These visualizations help us to explore the structure of geographic graphs as well as communicate their properties to a wide audience.
Arthur van Goethem
Algorithms for Curved Schematization (PDF
Schematization is the process of creating a simplified and compact representation of the input data. It can structure and simplify information, reduce the illusion of accuracy, and help create a striking and powerful message. In this thesis we look at possibilities for automated schematization using curves. We present different algorithms that may be used to schematize territorial outlines or networks. Algorithms are presented that allow the use of different curves, the introduction of new vertices, and schematization across junction points. Furthermore we also discuss linear cartograms and provide an alternative model where distortion is restricted to the (road) network. An efficient algorithm is described to compute a possible placement of all edges. Lastly we explore the limits of schematization. Traditional schematization considers shape schematization as a schematization of the boundary of a shape. We present a radically different type of geometric abstraction - the stenomap. Stenomaps represent two-dimensional input shapes by smoothly curving linear glyphs.
Cartographic Modelling for Automated Map Generation (PDF
For many applications, maps are the most effective visualisation of geographic phenomena. Automated map generation, once thought to be impossible, has celebrated great successes in recent years. These successes were concentrated on large-scale topographic map production and roadmap-style web-maps. Many more specialised map types, especially from the realm of thematic maps, remain challenges both interesting and relevant. The previous efforts were especially successful when the crucial design specifications were well understood and properly formalised. When these preconditions were met, algorithmic and technical refinement could take over. In this thesis we investigate several areas of cartographic design specifications that have so far been mostly neglected. We concentrate on cartographic modelling for map labelling and medium-scale map generation. We put a special focus on automated schematisation for chorematic diagrams.
Similarity Measures and Algorithms for Cartographic Schematization (PDF
A schematic map focuses on displaying specific information rather than full geographic detail. Such a map uses few geometric elements to convey a geographic shape. The geometry often adheres to a certain style, such as the octilinear style which only permits horizontal, vertical and 45-degree diagonal lines. For a map to be effective, geographic shapes such as countries and provinces must still be recognizable. In this thesis we investigate similarity measures and algorithms in the context of automated cartographic schematization, the process of creating schematic maps. Similarity measures are required to quantify resemblance between schematic and geographic shapes. We improve an existing similarity measure and develop new algorithms to compute schematic representations that resemble the geographic shapes.
Kinetic Data Structures in the Black-Box Model (PDF
In recent years there has been a growing interest in maintaining geometric data structures as the input moves over time. The straightforward approach is to recompute the structure from scratch whenever the input changes, but this can be wasteful if the changes are small. To avoid unnecessary computations, Kinetic Data Structures were introduced by Basch, Guibas and Hershberger in 1997. In this framework we assume that the trajectories of the objects are known and we can compute when to change the data structure. This leads to an event-driven approach for which several efficiency guarantees can be proven. Unfortunately, there are many situations when the trajectories are unknown. For these applications we introduce the black-box model to model the motions of the input and design efficient algorithms to maintain several basic data structures within this model.
Algorithms for Cartographic Visualization (PDF
Maps play an important role in our society. We use maps to find our way from one place to another, or to locate points of interest, like hotels, restaurants, and tourist attractions. But maps not only help us navigate through our environment. They are effective tools for communicating various types of information and help people to make decisions in, for example, spatial planning and politics. Recent technological advances and the changing needs of map users require maps to be created on-demand. Hence we need methods for the automated construction of maps. In this thesis we consider the automated construction of thematic maps, in particular schematic maps, cartograms, necklace maps, and flow maps. We study the underlying algorithmic problems and we present efficient algorithms to construct these maps.
Drawing Graphs for Cartographic Applications (PDF
Graphs are ubiquitous in computer science, and visualizing them in a good way has become the topic of the research area known as graph drawing. It combines techniques from graph theory, algorithms, (computational) geometry, and (computational) topology, and has applications to cartography, VLSI design, and information visualization, among others. This thesis studies three graph drawing problems. The first problem is the construction of rectilinear cartograms, where each region on a map is deformed into a rectilinear polygon whose area represents some value associated with the area (say, the population of a country). The resulting cartogram should resemble the original map as closely as possible in terms of shapes and adjacencies of the regions, while at the same time faithfully representing the value associated with each region. The second problem concerns cased drawings of graphs, where edge crossings are drawn in a way that suggests that one edge goes underneath the other. The third problem is to decide for certain curves and surfaces whether they could occur as the boundary of some shape.
Mohammad Ali Abam
New Data Structures and Algorithms for Mobile Data (PDF
Motion is ubiquitous in the physical world and due to recent advances in sensing and tracking technology, motion data is becoming more and more available in a variety of areas: air-traffic control, mobile communication, geographic information systems, and so on. It is not surprising, therefore, that in these applications areas of computer science it is necessary to store, analyze, and create or manipulate motion data. As a result, algorithms and data structures for moving objects have become an important area of study within the field of computational geometry. This thesis presents a number of new and fundamental results in this exciting area of research.