Labeling Lines and Areas in Dynamic Maps

How to automatically label a static map has been studied in cartography and computational geom- etry over the last three decades. From an algorithmic point of view, extensive research has gone into understanding the computational complexity and algorithms for the underlying optimization problems. Nowadays though, many maps that we use everyday are dynamic, allowing the user to zoom, rotate, or filter the shown content. Over the last ten years researchers at the intersection of cartography and computational geometry have developed first models and algorithms to study this problem for point features. In my research I will investigate how the two remaining feature types, namely lines and areas, can be labeled in dynamic maps. In this setting, neither of them has seen a rigorous treatment from the algorithmic point of view. In short, my aims are: Develop the first systematic model to label line and area features. Investigate how fast the resulting optimization problems can be solved. - Include more cartographic guidelines into the process. Provide prototype implementations to the research community. In my approach I will follow the ideas and concepts presented in the Active Range Model and design compatible models for line and area features. This model has been very successful in the study of labeling point features in dynamic maps and keeping my results compatible will allow for a future unified system to label all feature types. My goal here is to study the modeling and resulting algorithmic questions for lines and areas. Since the underlying optimization problems are likely NP-hard, I will focus on a fine- grained complexity analysis and approximation algorithms. To ensure the practical applicability of the algorithmic results, I will apply the methodology of algorithm engineering to turn theoretical advances into practical algorithms. The key idea being that algorithms should be developed in a continuous cycle of theory, implementation, and evaluation.

The lettering of a cartographic map concerns all its visible text. To this day the quality of human cartographers undertaking this task cannot be achieved by computers. However, there is a growing need to find good algorithms to place the text on maps in settings were handmade placements are unfeasible. Most notably this is the case in online systems such as Openstreetmap or Google Maps. Here, the sheer amount of labels and the changeful nature of the system makes placing the labels by hand not viable. Good map lettering though matters beyond its aesthetics. To give an example, when zooming into a map on a phone or on the screen, we use the features and text of the map to orient ourselves. If the text is occluded, unimportant text is shown too early, or the text changes all the time it gets harder for the user to interact with the system. In the end though finding good computer programs to undertake this task has proven to be challenging when we go beyond good-enough. In this project we investigated fundamental geometric properties of labeling maps of this kind. We identified several parts of such systems that are computationally hard to solve, establishing mathematical limits to what the machine can solve. While this might seem disappointing, better understanding these limitations is crucial to improving existing systems that have to work in a heuristic fashion.