Diese Arbeit befasst sich mit der automatischen Platzierung von Point-of-Interest (POI)-Labels in digitalen Karten. Dazu wurde das Wachstumsmodell für Kreise von Funke et al. auf achsenparallele Rechtecke übertragen, um die Form von Textlabels realitätsnäher zu berücksichtigen. Die zentrale Herausforderung besteht darin, möglichst viele Labels darzustellen, Überlappungen zu vermeiden, Konsistenz über verschiedene Zoomstufen hinweg sicherzustellen und gleichzeitig Verfahren zu entwickeln, die auch auf sehr großen Datensätzen wie OpenStreetMap (OSM) effizient einsetzbar sind.

Theoretisch konnten obere Laufzeitschranken für zwei Varianten von dem Algorithmus (Chebyshev- Nearest-Neighbor- und Euclidean-Nearest-Neighbor-basiert) unter Einsatz kombinierter Datenstrukturen hergeleitet werden. Für den praktischen Einsatz ergibt sich dabei eine effektive Laufzeitvon š¯‘‚(š¯‘› log^4 š¯‘›), wobei der Speicherbedarf š¯‘‚(š¯‘› log š¯‘›) für die CNN-Variante und š¯‘‚(š¯‘›) für die ENN-Variante beträgt. Beide Ansätze wurden implementiert und in Verbindung mit einem Quadtree ausgewertet.

Die Experimente zeigten, dass beide Verfahren identische Ergebnisse liefern, die ENN-Variante jedoch schnellere Berechnungszeiten erreicht. Für den Planetendatensatz mit 12,5 Millionen Labels konnten die Kollisionszeiten in weniger als 25 Minuten berechnet werden. Ein anschließender Webserver-Prototyp zur Abfrage der vorberechneten Daten zeigte, dass Suchanfragen in wenigen Millisekunden beantwortet werden können.

Damit leistet die Arbeit sowohl einen theoretischen als auch einen praktischen Beitrag zur effizienten und skalierbaren Vorberechnung von Labelhierarchien in interaktiven Kartendiensten.