CG/2015-Hauptklausur Aufgabe 5 c (4)

[bjuergens]

Frage: "Gegegeben sind zwei Objektmengen und zu jeder Men- ge ihr optimaler Hüllkörper. Der Aufwand, den optimalen Hüllkörper für alle Objekte zu bestimmen, ist unabhängig von der Anzahl der Objekte." Antwort (Ist): AABB und Kugel.

Fehler: Trifft meiner Meinung nach nicht auf Kugel zu.

Beispiel:

• Rot: 4 Punkte
• Gelb: Kugel um die Beiden linken Punkte
• Grün: Kugel um die beiden rechten Punkte
• Hellblau: Kugel, die alle 4 Punkte einschließt
• Dunkelblau: Kugel, die gelbe und grüne Kugel einschließt.

Wenn ich die grünen und den gelben Hüllkörper vereinigen will, weiß ich nicht, ob mein Ergebnis die hellblaue oder die Dunkelblau Kugel (oder irgendetwas dazwischen) ist. Ich muss also über alle Punkte iterieren um zu schauen, um den neuen Hüllkörper zu bestimmen

[MartinThoma]

Super Beispiel. Sehe ich auch so. Wenn es noch jemand bestätigt wäre es toll, wenn man das (inclusive dem Beispiel) in die Musterlösung nehmen könnte.

[MartinThoma]

Anmerkung: Angenommen, man hat nicht den entarteten Fall, dass mehr als 3 Punkte auf der Hülle der Kugel sind. Selbst dann hilft es nicht, wie man an einem leicht verändertem Beispiel von @wotanii sehen kann.

[childen]

+1