@phdthesis{Brummer2022, author = {Brummer, Stephan}, title = {Numerisch robuste Berechnung der zirkul{\"a}ren Sichtbarkeitsmenge}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-12299}, school = {Universit{\"a}t Passau}, pages = {viii, 170 Seiten}, year = {2022}, abstract = {Sichtbarkeitsprobleme, wie das Folgende, geh{\"o}ren zu den grundlegenden Problemen der algorithmischen Geometrie: Berechne zu einem einfachen Polygon, dem sogenannten Kanal, und zu einem darin enthaltenen Punkt die von diesem Punkt aus sichtbare Punktmenge. Dabei ist ein Punkt von einem anderen Punkt aus sichtbar, wenn deren Verbindungsstrecke den Kanal nicht verl{\"a}sst. Wir wollen uns in dieser Arbeit mit zirkul{\"a}rer Sichtbarkeit besch{\"a}ftigen. Zur Verbindung zweier Punkte sind dann nicht nur Strecken, sondern auch Kreisb{\"o}gen zul{\"a}ssig. Außerdem betrachten wir als Ausgangspunkt dieser sogenannten Sichtbarkeitskreisb{\"o}gen und -strecken eine Kante des Kanals anstatt eines einzelnen Punkts. Konkret liefert diese Arbeit einen Beitrag zur numerisch robusten Bestimmung der zirkul{\"a}ren Sichtbarkeitsmenge ausgehend von einer Kante des Kanals. Hierf{\"u}r wird in dieser Arbeit ein Algorithmus vorgestellt, mit dem f{\"u}r einen gegebenen Punkt festgestellt werden kann, ob dieser von der Startkante aus sichtbar ist. Im Fall eines sichtbaren Punkts wird ein Sichtbarkeitskreisbogen berechnet, der zwei Kanalber{\"u}hrungen besitzt. Damit kann der Algorithmus bei geeigneter Wahl des zu untersuchenden Punkts - der als dritte Kanalber{\"u}hrung fungiert - direkt zur Berechnung von sogenannten Grenzkreisb{\"o}gen der Sichtbarkeitsmenge benutzt werden. Diese definieren den Rand der zirkul{\"a}ren Sichtbarkeitsmenge und zeichnen sich dadurch aus, dass sie vom Kanal dreimal abwechselnd von links und von rechts ber{\"u}hrt werden. Der beschriebene Algorithmus basiert auf der Untersuchung derjenigen Kreisb{\"o}gen, die zwar nicht notwendigerweise vollst{\"a}ndig im Kanal liegen, aber die Startkante mit dem Punkt verbinden, dessen Sichtbarkeit bestimmt werden soll. Insbesondere werden dabei die Bereiche untersucht, in denen der jeweilige Kreisbogen den Kanal verl{\"a}sst, die sogenannten Verletzungen. Da die „Schwere" einer solchen Verletzung quantifizierbar ist, wird ein iteratives Vorgehen erm{\"o}glicht. Dabei wird der Kreisbogen iterativ so ver{\"a}ndert, dass dieser bei gleichem Endpunkt den Kanal immer „weniger verl{\"a}sst". Ist der Endpunkt und damit der zu untersuchende Punkt nicht sichtbar, wird im Laufe des Algorithmus festgestellt, dass keine derartige Verbesserung m{\"o}glich ist. Der vorgestellte Algorithmus ist numerisch robust, einfach umzusetzen und besitzt eine in der Anzahl der Kanalecken lineare Laufzeit.}, language = {de} }