Similarity measures
Set visualization
Vernacular regions

Research overview

This page will give you an overview of my research. For a comprehensive list of publications, please refer to the publications page.

Schematization: less is more

Geovisualization and cartographic maps aim for conveying data, structures and relations in their spatial context. Crucial is to emphasize the data and omit any distractors. In many cases, precise geography is not necessary to analyze data or to convey the main message. Automated simplification (detail reduction) hence plays a key role in systems to compute effective visual representations. Schematization takes this one step further, using stylistic rules to further structure space. Both are also important operators for generalization, the process of deriving a small-scale map from a large-scale one.

Since Harry Beck's original design of the London Underground map, octilinear or other straight-line restricted forms of schematization have been the norm. However, in recent years, curved schematization has been gaining in popularity.

Relevant publications

Similarity measures: comparing two shapes

Many problems ask for a comparison between curves. Many measures have been proposed to quantify similarity, for example, the Hausdorff and Fréchet distance. The Fréchet distance can be computed in O(n^2 log n) time using a dynamic program for the decision problem together with parametric search. This was shown in 1995 by Alt and Godau. We give the first asymptotic improvement for the general case by precomputing small parts of the decision problem, as well as a quadratic-time algorithm for approximating the Fréchet distance.

The Fréchet distance and many other measures result in a single number to quantify the similarity. However, many applications require a matching of the curves, a qualitative description of the actual similarity. In order to specify and compute high quality matchings for polygonal curves, we introduced a criterion called local correctness. This criterion describes a "good matching" for matching-based similarity measures such as the Fréchet distance. Informally, it states that a good matching for two curves predicts the similarity (according to the measure) for any matched subcurves.

Relevant publications

Set visualization: showing groups elements

Set visualization aims to support the analysis of sets and their relations. In many scenarios, the data points that are contained in the sets represent geographic locations. It is then often desirable to visualize these on a map at their correct location and overlay this map with a visualization that indicates the set memberships.

To tackle this problem, we present a method called KelpFusion. It uses a spanning graph, called the shortest-path graph, with routed edges to avoid visual clutter and fills faces to form clusters. In style, it lies in between hull-based methods like BubbleSets and line-based methods like LineSets and Kelp Diagrams.

Relevant publications

Vernacular regions: the shape of a set of points

A vernacular region is a region without a precise or administrative boundary. A formalization is needed to model these regions for automated usage. This allows for more intelligent treatment of search queries like “hotels in the British Midlands”. A common approach is to use the internet as a source of information, using search engines to relate exact geographical locations to vernacular regions. The question arises how to find the (approximate) boundary of a region, given a set of points that are likely to be inside or near the region.

What is the shape that these points describe? We developed shortest-path graphs, a new spanner-like geometric model, that is scale-independent, and density-sensitive. Moreover, based on a single parameter, it varies from the Euclidean minimal spanning tree to the convex hull of the point set.

We also consider some straightforward extensions to include geographic context (e.g. country borders) in computing a vernacular region. This same extension can also be applied to the popular KDE method.

Relevant publications