Karlsruher Institut f¨ ur Technologie



Yüklə 25,37 Kb.
Pdf görüntüsü
tarix05.01.2018
ölçüsü25,37 Kb.
#19726


Karlsruher Institut f¨

ur Technologie

Algorithmische Geometrie

Fakult¨


at f¨

ur Informatik

Sommersemester 2011

ITI Wagner

Martin N¨

ollenburg/Andreas Gemsa

Musterl¨

osung f¨


ur ¨

Ubungsblatt 2

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. Gebe einen Algorithmus an, der ¨

uberpr¨


uft ob P ein einfaches (d.h.

schnittfreies) Polygon ist. Der Algorithmus soll eine worst-case Zeitkomplexit¨at von O(n log n)

haben.



osung:



Modifikation des Algorithmus aus der Vorlesung: Breche nach dem ersten Schnitt ab. Damit ist

k

konstant und die Laufzeit O(n log n) folgt automatisch.



2

Weniger Speicherplatzverbrauch

Der Algorithmus zur Bestimmung von Schnitten zweier Segmente aus der Vorlesung ben¨otigt

O(n + k) Speicher. Modifziere den Algorithmus so, dass der Speicherplatzbedarf auf O(n) redu-

ziert wird.

osung:



Idee: Speichere nur die Schnittpunkte von benachbarten Kanten (bzgl. der aktuellen Position der

Sweep Line). Dann gibt es nur O(n) viele solcher Punkte und der Speicherplatzbedarf sinkt auf

O(n). Dazu f¨

uge Schnittpunkte nur von benachbarten Kanten ein und entferne Schnittpunkte

von Kanten die im Verlauf des Algorithmus keine Nachbarn sind. Diese Schnittpunkte werden

erst wieder eingef¨

ugt wenn beide Kanten Nachbarn sind.



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) Zeige, dass der gr¨oßte rechte obere Bereich eines Punktes entweder ein Quadrat oder der

Schnitt zweier offener Halbebenen ist.

b) ¨


Uberlege f¨

ur einen Punkt p ∈ P und jeden der beiden zugeh¨origen Oktanten (vgl. Abbil-

dung 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 Oktanten



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. Berechne 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).

osung:



Zu a):

Wenn kein Punkt im oberen oder rechten Oktanten von p ist, dann ist der gr¨oßte rechte obere

Bereich (groB) offensichtlich der Schnitt zweier offener Halbebenen ist.

Seien nun der rechte und obere Oktant von p nicht leer. Die Menge der Punkte im rechten und

oberen Oktanten von p sei R. Dann gibt es ein Quadrat Q im groB welches durch die Punkte

p

und q ∈ R induziert wird (untere linke Ecke ist fest und vertikaler bzw. horizontaler Abstand



von p und q legt die Seitenl¨ange fest). Es kann kein gr¨oßeres Quadrat im groB geben, da so ein

Quadrat den Punkt q enthalten w¨

urde. Da alle Quadrate die im groB enthalten sind kleiner als

Q

sind und sich mit Q die linke untere Ecke teilen muss der groB in diesem Fall ein Quadrat



sein.

Zu b):


Die Menge der Punkte im rechten und oberen Oktanten von p sei R. Entscheidend ist hier der

Punkt p


r

∈ R im rechten Oktant, der den geringsten horizontalen Abstand zu p hat und analog

der Punkt p

o

∈ R im oberen Oktant, der den geringsten vertikalen Abstand zu p hat. Das ist



leicht ersichtlich wenn wir die Punkte aus R, die im rechten Oktanten liegen vertikal auf die


Begrenzungslinie zwischen dem oberen und rechten Oktanten projizieren. Jedes Quadrat, dass

nicht durch p

r

begrenzt wird enth¨alt wenigstens p



r

und somit w¨

urde dieses Quadrat nicht den

groB begrenzen (analoge Argumentation f¨

ur p

o

und den oberen Oktanten).



Zu c):

L¨osung ben¨otigt zwei Sweeps (s. Hinweis). Hier wird nur der Sweep f¨

ur die Bestimmung der

Punkte im rechten Oktant beschrieben. Der zweite Sweep-Vorgang l¨auft analog.

Gesweept wird von unten nach oben. Außerdem verwalten wir eine nach y-Koordinaten sortierte

Liste L von bisher besuchten Knoten die aber noch keinen ’Extrempunkt’ im rechten Quadranten

zugewiesen bekommen haben. Trifft die Sweep-Line einen Knoten p so testen ob dieser Knoten

im rechten Quadranten des obersten Knotens q aus L liegt. Ist das der Fall entfernen wir q aus

L und markieren f¨

ur q den Knoten p als ’Extrempunkt’ ein. Wir wiederholen den Test von p mit

dem obersten Knoten aus L solange bis der Test fehlschl¨agt. Danach tragen wir p an oberster

Stelle in L ein und die Sweep-Line f¨ahrt fort zum n¨achsten Knoten. Ein beispielhafter Ablauf

dieses Algorithmus wird in Abbildung 2 dargestellt.

Wir m¨


ussen die Knoten sortieren O(n log n) und die Menge der Knoten durchlaufen (Sweep-

Line) O(n). Der Test ob ein Knoten im rechten Oktanten eines anderen liegt geht in O(1) und

wir f¨

uhren maximal O(n) solcher Tests durch (In jedem Schritt f¨



uhren wir entweder einen Test

durch, oder wir reduzieren die Anzahl der Knoten der Liste L um mindestens k − 1, wobei k die

Anzahl der Tests in einem Durchlauf sind). Wir bleiben also in der geforderten Laufzeit.

Es bleibt zu zeigen, dass der Algorithmus korrekt ist. Dazu folgt ihr die Beweisidee: Angenommen

die Sweep-Line ist momentan bei Knoten p, der oberste Knoten in L ist q. Außerdem ist p nicht

im rechten Quadraten von q aber der Extrempunkt im rechten Quadraten eines Knotens q der

in L enthalten ist, aber nicht der oberste Knoten ist. Da p nicht im rechten Quadranten von q

liegt, aber im rechten Quadranten von q muss q links von q liegen. Dann liegt aber q im rechten

Quadraten von q und w¨are der ’Extrempunkt’ f¨

ur q . Widerspruch.




Sw

eep


Ric

h

tung



Sw

eep


Ric

h

tung



Sw

eep


Ric

h

tung



Sw

eep


Ric

h

tung



Sw

eep


Ric

h

tung



Abbildung 2: Beispiel f¨

ur den Algorithmus zur L¨osung von 3c). Rote Pfeile markieren den ersten

Knoten der ¨

uberpr¨


uft, blaue die Folgenden.

Yüklə 25,37 Kb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə