Efficient visibility queries in simple polygons (Q1862134): Difference between revisions

Die Autoren entwickeln Algorithmen zur Lösung des folgenden Sichtbarkeitsproblems und nahe verwandter Probleme: In der euklidischen Ebene \(E^2\) werden Polygone betrachtet (einfach zusammenhängende Teilmengen in \(E^2\), deren Rand eine geschlossene Kette von Strecken ist). Ein Polygon \(P\) wird durch seine aufeinanderfolgenden Ecken definiert; keine drei Ecken seien kollinear. Die Punkte eines Polygons \(P\) seien die Punkte des Inneren und des Randes von \(P\). Die Sprechweise ``zwei Polygonpunkte sehen einander'' bedeute, dass ihre Verbindungsstrecke keinen Punkt des Polygonäußeren enthält. Gesucht werden alle Polygonecken, die von einem gegebenen Augpunkt \(x\in P\) aus sichtbar sind (bzw. die \(x\) sehen). Der entwickelte Algorithmus findet diese Ecken in der Zeit \(O(\log n)\). Die Menge der Polygonpunkte, die von einem Augpunkt \(x\in P\) aus sichtbar sind, heißt das Sichtbarkeitspolygon von \(x\). Ein Hauptresultat der Arbeit besagt, dass sich das Sichtbarkeitspolygon von \(x\) in der Zeit \(O(\log n+k)\) ermitteln läßt, wobei \(k\) die ``Größe'' des Sichtbarkeitspolygons angibt. Als zentrales Hilfsmittel wird die Zerlegung eines Polygons \(P\) in Sichtbarkeitsbereiche verwendet. Es handelt sich dabei um die maximal zusammenhängenden Teilmengen von \(P\), deren Punkte dieselben Ecken von \(P\) sehen. Ein Polygon \(P\) besitzt \(O(n^3)\) Sichtbarkeitsbereiche (die stets konvex sind) und \(O(n^2)\) Bereiche, aus deren Punkten die minimale Anzahl von Polygonecken sichtbar ist; diese Ergebnisse sind scharf. Der zur Polygonzerlegung gehörende gerichtete duale planare Graph dient als weiteres zentrales Hilfsmittel. Er wird wesentlich herangezogen bei der Ermittlung der (im Polygon \(P\) vorliegenden) Aufeinanderfolge der Polygonecken, die von einem Augpunkt \(x\) aus zu sehen sind und damit bei der Bestimmung des Sichtbarkeitspolygons von \(x\). Es folgt die Erweiterung der Lösungsideen auf Augpunkte \(x\), die außerhalb eines Polygons \(P\) liegen. Dabei ist zu beachten, ob \(x\) innerhalb oder außerhalb der konvexen Hülle von \(P\) liegt. Abschließend wird beschrieben wie sich die Ecken eines Polygons \(P\) ermitteln lassen, die eine (innerhalb oder außerhalb von \(P\)) vorgegebene Strecke vollständig oder teilweise sehen. Die reichhaltige Arbeit schließt mit weiterführenden Fragen.