Musterlösung Blatt 8 H-30: Notation: a = [p1,p2] bezeichne die Strecke von p1 nach p2. Es sei a = [p1,p2] mit p1=(1/2,-2), p2=(3/2,1) b = [p3,p4] mit p3=(-2,1), p4=(1,1/2) c = [p5,p6] mit p5=(-3,1), p6=(1,2) d = [p7,p8] mit p7=(0,-3), p8=(4,1) e = [p9,p10] mit p9 =(-1,5/2), p10=(3,1) f = [p11,p12] mit p11=(-4,-1), p12=(1,0) Ereignispunkte sortiert nach x- und y-Koordinaten: p11, p5, p3, p9, p7, p1, p12, p4, p6, p2, p10, p8 Ereignispunkt p11: f wird einsortiert Baum: (f) (hier als Liste geschrieben) Ereignispunkt p5: c wird einsortiert Baum: (f,c) Test: Intersect(c,f) liefert false Ereignispunkt p3: b wird einsortiert Baum: (f,b,c) Test: Intersect(b,c) liefert false Intersect(b,f) liefert false Ereignispunkt p9: e wird einsortiert Baum: (f,b,c,e) Test: Intersect(e,c) liefert true Algorithmus bricht ab und liefert true. H-31: Siehe die Musterlösung von Andreas Abel. H-32: Seien die Punkte p1 bis p9 in der Reihenfolge, wie sie in der Angabe stehen. Unterster Punkt ist p1. Punkte nach Polarwinkel mit p1 sortiert: p1, p5, p6, p7, p2, p3, p8, p4, p9 Stack am Anfang: (p1,p5,p6) Test: [p5,p6] [p6,p7] bildet Linkskurve push(p7) (p1,p5,p6,p7) Test: [p6,p7] [p7,p2] bildet Rechtskurve pop (p1,p5,p6) Test: [p5,p6] [p6,p2] bildet Linkskurve push(p2) (p1,p5,p6,p2) Test: [p6,p2] [p2,p3] bildet Rechtskurve pop (p1,p5,p6) Test: [p5,p6] [p6,p3] bildet Linkskurve push(p3) (p1,p5,p6,p3) Test: [p6,p3] [p3,p8] bildet Rechtskurve pop (p1,p5,p6) Test: [p5,p6] [p6,p8] bildet Linkskurve push(p8) (p1,p5,p6,p8) Test: [p6,p8] [p8,p4] bildet Linkskurve push(p4) (p1,p5,p6,p8,p4) Test: [p8,p4] [p4,p9] bildet Rechtskurve pop (p1,p5,p6,p8) Test: [p6,p8] [p8,p9] bildet Linkskurve push(p9) (p1,p5,p6,p8,p9) Also sind die Eckpunkte der konvexen Hülle p1 , p5, p6, p8, p9 H-33: Der Algorithmus muss wie folgt modifiziert werden: Zunächst muss beim Basisfall (höchstens drei Punkte) natürlich dasjenige Paar mit der kleinsten Manhattan- Distanz gefunden werden. Sonst wird, wie gehabt, die Menge durch eine senkrechte Gerade l in zwei Hälften PL und PR geteilt und diese rekursiv behandelt; der gefundene Minimalabstand sei delta. Paare mit geringerem Abstand können nun nur noch je einen Punkt aus PL und einen aus PR enthalten, und in einem Streifen [l-delta,l+delta] liegen. Werden die Punkte nach y-Koordinaten sortiert und von unten nach oben beetrachtet, muss nun aber jeder Punkt mit den 9 (statt 7) größeren verglichen werden, da in einem Rechteck der Größe (2delta*delta) 10 Kandidaten liegen können: in einem Quadrat der Seitenlänge delta können 5 Punkte mit Manhattan-Distanz delta liegen, gemäß dem folgenden Muster: *-----* | | | | | * | | | | | *-----*