Karlsruher Institut f¨ ur Technologie
Yüklə 12,96 Kb. Pdf görüntüsü
|
| Karlsruher Institut f¨ ur Technologie Algorithmische Geometrie Fakult¨
at f¨ ur Informatik Sommersemester 2014 ITI Wagner Martin N¨ ollenburg/Benjamin Niedermann ¨ Ubungsblatt 2 (L¨ osung) Ausgabe:
Dienstag 22. April 2014 Abgabe:
Dienstag 29. April 2014 1 Einfaches Polygon? In der Vorlesung wurde ein Verfahren vorgestellt mit dem man Schnitte zwischen beliebigen Segmenten in O((n + k) log n) bestimmen kann. Wir betrachten hier ein verwandtes Problem. Gegeben sei ein Polygon P. Geben Sie einen Algorithmus an, der ¨ uberpr¨
uft ob P ein einfa- ches (d.h. schnittfreies) Polygon ist. Der Algorithmus soll eine worst-case Zeitkomplexit¨ at von O(n log n) haben. L¨ osung: Modifikation des Algorithmus aus der Vorlesung: Beachte ein Polygon hat genau n Schnittpunkte (Strecken schneiden sich an Knoten des Polygons). F¨ uhre den Algorithmus aus und breche ab sobald der Algorithmus mehr als n Schnittpunkte erkannt hat und gebe aus, dass das Polygon nicht einfach ist. In diesem Fall ist k = n + 1. Damit ist die Laufzeit in O((n + n + 1) log n) = O(2n log n) = O(n log n). 2 Weniger Speicherplatzverbrauch Der Algorithmus zur Bestimmung von Schnitten gegebener Segmente aus der Vorlesung ben¨ otigt
O(n + k) Speicher. Modifzieren Sie den Algorithmus so, dass der Speicherplatzbedarf auf O(n) reduziert wird. L¨ osung: Speichere nur die Schnittpunkte von benachbarten Kanten (bzgl. der aktuellen Position der Sweep Line). Es gibt nur O(n) viele solcher Punkte und der Speicherplatzbedarf sinkt auf O(n). Um dies zu erreichen, f¨ uge nur Schnittpunkte von benachbarten Kanten ein und entferne Schnittpunkte von Kanten die im Verlauf des Algorithmus keine direkt Nachbarn mehr sind. Diese Schnittpunkte werden erst dann wieder eingef¨ ugt wenn beide Kanten erneut Nachbarn werden.
3 Sweepen
Gegeben sei eine endliche Menge P von Punkten in der Ebene. Der gr¨ oßte rechte obere Bereich eines Punkes p ∈ P ist die Vereinigung aller offenen achsenparallelen Quadrate, die p mit ihrer linken unteren Ecke ber¨ uhren und keinen Punkt aus P in ihrem Inneren enthalten. a) Zeigen Sie, dass der gr¨ oßte rechte obere Bereich eines Punktes entweder ein Quadrat oder der Schnitt zweier offener Halbebenen ist. b) ¨ Uberlegen Sie f¨ ur einen Punkt p ∈ P und jeden der beiden zugeh¨ origen Oktanten (vgl. Ab- bildung 1), welche Punkte aus P im jeweiligen Oktant den gr¨ oßten rechten oberen Bereich von p am st¨ arksten einschr¨ anken. Reicht die Kenntnis dieser Punkte aus den beiden Ok- tanten aus, um den gr¨ oßten rechten oberen Bereich von p zu bestimmen? p oberer Oktant rechter
Oktant Abbildung 1: Oberer und rechter Oktant zum Punkt p c) Gegeben sei eine Menge P von n Punkten. Berechnen Sie f¨ ur jeden Punkt aus P den gr¨ oßten rechten oberen Bereich mit einer Gesamtlaufzeit von O(n log n). Hinweis: Sweepe die Ebene zweimal und ermittle dabei die Punkte aus Teilaufgabe b). L¨
Ubung vom 30.04.2014. Yüklə 12,96 Kb. Dostları ilə paylaş:
|