Algorithms for Geovisualization

A significant part of today's data is geographic, has a geographic component (is geo-referenced), or benefits from geographic interpretation. To analyze these data requires advanced algorithmic tools. Problems in this domain are often ill-defined, relying on intuitive notions, and hence require a modeling step to define a concrete algorithmic problem before it can be solved. There is often a trade-off between simple-but-imperfect models that can be solved well with algorithms, and very complex models that cannot be solved adequately with algorithmic techniques. In this course, we look at the interaction such modeling and the necessary algorithms to solve the resulting problems.

We focus on such problems in geovisualization (or automated cartography), that is, to compute high-quality visualizations (maps) of geographic data. We will occasionally also side-step to other, related topics using geographic data or in information visualization to see general applications of the above-metioned trade-off. We will, for example, study concepts and algorithms for:

• Similarity

• General-purpose maps, such as simplification and labeling

• Thematic maps, such as symbol maps and cartograms.

• Movement analysis

• Information visualization of nongeographic data

In order to successfully take this course, you should already have a basic knowledge of algorithms and mathematics. Here's a short list of what you are supposed to know:
• O-notation, Ω-notation, Θ-notation; how to analyze algorithms
• Basic calculus: manipulating summations, solving recurrences, working with logarithms, etc.
• Basic probability theory: events, probability distributions, random variables, expected values etc.
• Basic data structures: linked lists, stacks, queues
• (Balanced) binary search trees
• Basic sorting algorithms, for example MergeSort, InsertionSort, QuickSort
• Graph terminology, representations of graphs (adjacency lists and adjacency matrix), basic graph algorithms (BFS, DFS, topological sort, shortest paths)
• Basic geometric terminology (polylines, polygons, simple polygons, intersections, etc.)
• Dynamic programming, greedy algorithms
• Basic complexity theory (NP-hardness, reductions; for understanding lectures only, not part of tested material)
All this can be found in “Introduction to Algorithms” by T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein (MIT Press, 2009).

Though basic familiarity with geometric concepts in algorithms is useful, Geometric Algorithms (2IMA15) is not a prerequisite.

At the end of this course students should be able to
• analyze and model problems in geovisualization in such a way as to allow algorithmic study
• describe and apply algorithms and data structures for fundamental problems in geovisualization
• develop algorithms to solve computational challenges in geovisualization

You must meet the following requirements

• Completed none of the course modules listed below
• Algorithms for geographic data (2IMG15)