Bachelorarbeit BCLR-2019-03

Sharma, Raman: Heuristics for the computation of map labelings using disk labels.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 3 (2019).
59 Seiten, englisch.

Computation of map labelings is a major challenge in the field of web mapping services. The main task is to get an understandable view of a map, which allows a person the rotating, panning and zooming of a currently displayed map area, by adequate labeling. For this, some requirements need to be fulfilled, such as handling the selection of labels, that are displayed simultaneously on the map, when zooming out of it. A solution has been implemented, that computes an elimination order of the labels. However, this solution is restricted to particular datasets, since it requires a total order over the labels. In this thesis, we optimize the algorithm by breaking up the total order, thus being able to apply this solution on real world datasets. Furthermore, we implement heuristics in the hope to keep as many centers alive for as long as possible. We then identify the best heuristic by comparing them to each other through quality measures. Additionally, we introduce a linear program, which computes the optimal elimination sequence of the labels, so we can conclude, how efficient our proposed algorithm is.

Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Algorithmik
BetreuerFunke, Prof. Stefan; Krumpe, Filip
Eingabedatum20. Mai 2019
   Publ. Informatik