05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
4 results
Search Results
Item Open Access OSCAR: a textual and spatial exploratory search engine for OpenStreetMap data(2020) Bahrdt, Daniel; Funke, Stefan (Prof. Dr.)Item Open Access Labeling interactive maps(2020) Krumpe, Filip; Funke, Stefan (Prof. Dr.)Navigationssysteme, beziehungsweise digitale Kartenapps, haben sich zu alltäglichen Begleitern entwickelt. Waren digitale Karten vor einem Jahrzehnt ein wertvolles Gut - Updates für Navigationssysteme wurden für viel Geld verkauft- sind sie heute durch die Verbreitung von Google Maps und Co. eine Selbstverständlichkeit. Neben der Verfügbarkeit und der Möglichkeit einfacher Updates, ermöglichen digitale Karten eine einfache, intuitive Interaktion. Das Zoomen, Verschieben und Drehen des Kartenausschnitts zum Erkunden von Details und der Ausrichtung in Blickrichtung des Nutzers, sind wohlbekannte Funktionen. Letzteres ist vor allem bei Navigationssystemen zentral. Dort wird die Kartenausrichtung generell in Fortbewegungsrichtung gewählt. Insbesondere für die Darstellung von Kartenbeschriftung, stellen diese Möglichkeiten eine Herausforderung dar. In der vorliegende Arbeit wird ein Konzept zur Gestaltung von Beschriftungen in interaktiven Karten, die stufenloses Zoomen, Verschieben und Rotieren des Kartenausschnitts ermöglichen, vorgestellt. Dabei wird insbesondere die Beschriftung von sogenannten ”Points of Interest” - also zu beschriftenden Punkten - thematisiert. Derartige Beschriftungen sind gewöhnlich horizontal ausgerichtet und überlappen sich somit tendenziell bei der Kartenrotation. Vor allem beim Zoomen der Karte sind verschiedene Konsistenzkriterien zu beachten - so soll beispielsweise eine Beschriftung während eines kontinuierlichen Zoomens nicht mehrfach hinzugefügt und wieder entfernt werden. Außerdem sollen Beschriftungen von wichtigeren Punkten länger sichtbar sein, als solche von weniger wichtigen Punkten. Bei der Beschriftung von Gebieten gilt, dass sich die Beschriftung im Gebiet befinden und die grobe Form des Gebiets adaptieren soll. Um letzteres zu erreichen, darf die Beschriftung entlang eines Kreisbogens gebogen sein. Rotation ist in diesem Szenario einfach - die Beschriftung muss lediglich in ihrer Ausrightung umgekehrt werden, sodass sie nicht auf dem Kopf steht. Beim Zoomen des Kartenausschnitts sollten Gebiete als Ganzes oder ihre Untergebiete beschriftet werden, abhängig von der Kartenskala der Gebietsbeschriftung. Für der Beschriftung von Punkten werden sogenannte ”Disk-Label” eingeführt. Bei diesen wird für jede Beschriftung ein kreisförmiger Bereich um den zu beschriftenden Punkt reserviert. Die Beschriftung des Punkts bleibt in beliebigen Ausrichtungen der Karte vollständig in diesem Bereich enthalten. Indem als Beschriftung in einer beliebigen Kartenskala eine überschneidungsfreie Untermenge der ”Disk-Label” gewählt wird, ist die lesbare Darstellung bei Rotation gewährleistet. Beim Herauszoomen aus dem Kartenausschnitt, werden die Beschriftungen bei konstanter Größe beibehalten. Entsprechend wachsen die zugehörigen Disks relativ zur Karte - entsprechend schrumpfen die Distanzen zwischen den Disks. Bei fortschreitendem Zoomen, kommt es zu Berührungen der Disks. Dabei muss eine der beteiligten Beschriftungen muss entfernt, um bei weiterem Zoomen die überschneidungsfreiheit zu erhalten. Wird der entsprechende Zoomprozess von ”unendlich 107weit hineingezoomt” zu ”unendlich weit herausgezoomt” betrachtet, ergibt sich eine sogenannte Eliminationssequenz der Beschriftungen. Diese kann für einen Datensatz im Voraus berechnet werden und ermöglicht dann eine einfache, effiziente Ableitung einer Kartenbeschriftung für ein gegebenes Darstellungszenario. Das Problem der Berechnung der Eliminationssequenzen kann verallgemeinert in einem d-dimensionalen Hyperraum betrachtet werden. Entsprechend der Disks in 2D, wachsen d-dimensionalen Hyperbälle. Eine Eiminationssequenz ist dabei nicht eindeutig - kollidieren Bälle der selben Wichtigkeit, ist die Entscheidung welcher der beiden Bälle eliminiert wird, essentiell für den weiteren Verlauf der Sequenz. Das Ziel ist die Berechnung einer optimalen Sequenz, in der die Summe aller Eliminationszeitpunkte maximiert wird. Es wird gezeit, dass die Berechnung einer solchen optimalen Sequenz N P − hart ist. Für ein vereinfachtes Szenario - in welchem die Sequenz eindeutig ist - wird ein effizientes Berechnungsverfahren vorgestellt und analysiert. Dieses Verfahren hängt stark von einer effizienten Methode zur Berechnung des nächsten Nachbarn sowie der Suche nach Punkten mit einer maximalen Distanz zu einem gegebenen Punkt ab. Je nach Szenario können diese Operationen effizienter oder weniger effizient gelöst werden. Für 2D und für höhere Dimmensionen werden zwei verschiedene theoretische Laufzeitschranken bewiesen. Für die praktische Beschriftung von digitalen Karten, werden Punkte auf einem virtuellen Globus betrachtet. Eine Berechnung der Sequenz für 13 Millionen Punkte ist auf einem herkömmlichen Computer in etwa 15 Minuten möglich. Das ursprüngliche, unvereinfachte Problem kann mittels eines Mixed-Integer Linearen Programms für wenige Punkte exakt gelöst werden. Allerdings nur mit erheblichem Rechen- und Speicheraufwand. Eine gute Approximation der optimalen Sequenz bieten Heuristiken. Mittels dieser kann der vorgestellte Algorithmus für das vereinfachte Szenario Lösungen für das unvereinfachte Problem berechnen. In der Güte liegen die Heuristiken bei 5% − 10% unter dem Optimum. Bei Berechnungszeiten von 15 − 20 Minuten auf einem herkömmlichen Computer. Eine Gebietsbeschriftung liegt vollständig innerhalb des Gebiets und ahmt die Form des Gebiets nach, indem sie entlang eines Kreisbogens plaziert ist. Für eine gute Beschriftung ist eine entsprechende Platzierung gesucht, welche die Größe der Beschriftung maximiert. Abhängig davon kann eine maximale und minimale Kartenskala berechnet werden, bei welcher die Beschriftung lesbar dargestellt werden kann. Entsprechend kann das Gebiet bei größeren Skalen in einer weiteren Verfeinerung dargestellt, oder bei kleineren Skalen durch eine Punkt-Beschriftung oder die Darstellung eines umfassenden Gebiets ersetzt werden. Für die Berechnung einer solchen guten Beschriftung wird in der vorliegenden Arbeit ein effizienter Algorithmus vorgestellt. Dieser basiert auf einem Algorithmus von 2001, von M. Barrault in [Mat01] publiziert. Durch verschiedene Optimierungen kann diese Berechnung auf Quasi-Echtzeit verbessert werden.Item Open Access Improved algorithms for map rendering and route planning(2020) Mendel, Thomas; Funke, Stefan (Prof. Dr.-Ing.)In dieser Arbeit werden verschiedene Teilbereiche der Kartendarstellung und der Wegefindung betrachtet. Der erste Teil beschäftigt sich mit Grenzvereinfachung und Gebietsbeschriftung. Der zweite Teil stellt ein beschleunigtes Verfahren zur Berechnung kürzester Wege vor.Item Open Access Automaton structures : decision problems and structure theory(2020) Wächter, Jan Philipp; Diekert, Volker (Prof. Dr.)This thesis is devoted to the class of automaton groups and semigroups, which has gained a reputation of containing groups and semigroups with special algebraic properties that are hard to find elsewhere. Both automaton groups and semigroups are studied from a structural and an algorithmic perspective. We motivate the use of partial automata as generating objects for algebraic structures and compare them to their complete counterparts. Additionally, we give further examples of semigroups that cannot be generated by finite automata and show that every inverse automaton semigroup is generated by a partial, invertible automaton. Moreover, we study the finite and infinite orbits of ω-words under the action induced by an automaton. Here, our main result is that every infinite automaton semigroup admits an ω-word with an infinite orbit. We apply these structural results algorithmically and show that the word problem for automaton groups and semigroups is PSpace-complete. Furthermore, we investigate a decision problem related to the freeness of automaton groups and semigroups: we show that it is undecidable whether a given automaton admits a non-trivial state sequences that acts trivially and we use this problem for further reductions. Afterwards, we strengthen Gillibert’s result on the undecidability of the finiteness problem for automaton semigroups and give a partial solution for the group case of the same problem. Finally, we consider algorithmic questions about increasing the orbits of finite words and apply these results to show that, among others, the finiteness problem for (subgroups of) automaton groups of bounded activity is decidable.