Generating stable demers Cartograms and Iso-Hexagon cartograms

Abstract

In dieser Arbeit behandeln wir das Thema der automatischen Generierung von stabilen Demers Kartogrammen und Iso-Hexagon Kartogrammen. Ein Demers Kartogramm/Iso-Hexagon Kartogramm ist eine Repräsentation von Daten auf einer Karte, in welcher alle Länder als Quadrate/reguläre Sechsecke dargestellt werden und die assoziierten Daten eines Landes die Größe diese Quadrats/regulären Sechsecks bestimmen. Diese Art von Kartogrammen ist beliebt um Unterschiede zwischen der Größe eines Landes und anderen georeferenzierten Daten aufzuzeigen, sowie um die Veränderung in diesen Daten über einen gewissen Zeitraum hinweg zu visualisieren. In diesen Serien von Kartogrammen, aber auch in einem Kartogramm generell, ist es von größter Wichtigkeit das mentale Modell des Betrachters so wenig wie möglich zu stören. Um dies zu erreichen, versuchen wir stabile Demers Kartogramme und Iso-Hexagon Kartogramme zu erstellen, die gewissen Quaitätskriterien---wie zum Beispiel benachbarte Regionen, wenn möglich, benachbart zu halten---entsprechen. Wir präsentieren darüber hinaus NP-Hardness Beweise für einige generalisierte Versionen der auftretenden Probleme sowie eine Methode, eine verlorene Adjazenz zwischen benachbarten Regionen in einem Iso-Hexagon Kartogramm zu visualisieren. Und schließlich präsentieren wir eine experimentelle Auswertung unseres Models.

In this thesis we approach the topic of automated generation of stable Demers cartograms and iso-hexagon cartograms. A Demers cartogram/iso-hexagon cartogram is a representation of a data set on a map, which represents each country as a square/regular hexagon and uses the associated data for every country to determine the size of this square/regular hexagon. These kinds of cartograms are widely used to visualize discrepancies between the size of a country and some other georeferenced data as well as to visualize the change of a data set over time. In these series of cartograms, but also in a cartogram in general, it is of vital importance to disturb the mental model of the user as little as possible. In order to achieve this, we try to create stable sets of cartograms, which fulfill certain quality criteria, like keeping as many adjacencies as possible. For this, we present an LP formulation which can be used to create stable sets of Demers cartograms and iso-hexagon cartograms. We further present a NP-hardness proof for a generalized version of some of the problems and present a method of visualizing lost adjacencies in a iso-hexagon cartogram. Finally we present an experimental evaluation of our model.