Fehler und Anmerkungen
Kurs Algorithmische Geometrie (1840)

in der Version vom Sommersemester 1997

Diese Fehlerliste wurde freundlicherweise vom Kursbetreuer Elmar Langetepe korrekturgelesen. Vielen der hier aufgeführten Punkte konnte er zustimmen. Bei einigen hat er Anmerkungen gemacht, die ich als Kommentare mit aufgenommen habe.

Index

Kurseinheit 1

Seite: Fehler / Anmerkung:
ii Die Überschrift von Kapitel 5 lautet Voronoi-Diagramme (nicht: "Distanzprobleme")
16 Letzter Absatz: "Wenn man zusätzlich für jede Kante Verweise auf ihre Nachfolgerkanten gegen den Uhrzeigersinn speichert" (nicht: "im Uhrzeigersinn", denn das wird bereits getan)
31 Übungsaufgabe 1.11: Hier fehlt die Definition des Begriffs "Binärbaum". Sie lautet folgendermaßen: Ein Binärbaum ist ein Baum, dessen Knoten entweder zwei oder kein Blatt haben.
(Dies ist nicht trivial, denn es gibt offensichtlich mehrere verschiedene Definitionen des Begriffs "Binärbaum").

Kurseinheit 2

Seite: Fehler / Anmerkung:
53 In dem Programm am Anfang der Seite müssen die beiden letzten Zeilen des else-Zweigs vertauscht werden (also zuerst MinSoFar := ... und dann rechts := ...), sonst wird im letzten Durchlauf auf P[n+1] zugegriffen.
66 Im Absatz unter der Abbildung: "Dann rotieren wir das alte XY-Koordinatenkreuz ... gegen den Uhrzeigersinn" (nicht: "im Uhrzeigersinn", denn die Punkte werden im Uhrzeigersinn gedreht)
78 In der Formel nach Korollar 2.17 ist auf der rechten Seite die Vereinigung der D_i gemeint (nicht der Durchschnitt)
79 Am Ende des Absatzes "Ereignisse": Ich würde hier schreiben: "wie bei der Bestimmung der Schnittpunkte von Liniensegmenten in Abschnitt 2.3.2" (nicht: "Durchschnitte", auch wenn es mathematisch auf dasselbe herauskommt, sofern sich vollständig überdeckende Linien ausgeschlossen sind. Außerdem heißt Abschnitt 2.3.2 auch so).

Kommentar von Elmar Langetepe: Hierin sehe ich keinen Fehler; eine Änderung der Formulierung scheint mir daher nicht zwingend notwendig.

Zurück zum Index

Kurseinheit 3

Seite: Fehler / Anmerkung:
97 3. Abschnitt: Ich würde hier schreiben "In der Praxis werden Daten ... wenn sie dauerhaft aufbewahrt werden sollen" (nicht: "auf Dauer benötigt werden", das bedeutet eher: "ständig innerhalb eines längeren Zeitraums verfügbar sein sollen")

Kommentar von Elmar Langetepe: Hierin sehe ich keinen Fehler; eine Änderung der Formulierung scheint mir daher nicht zwingend notwendig.

106 In Theorem 3.3 muß die Behauptung lauten: "E_W (r) \in O(E_V (r))" (dies wird zumindest im ersten Abschnitt des Beweises bewiesen)
107 Im 4. Abschnitt wird r_ij verwendet, ohne daß die r_k vorher eingeführt wurden.
110 Modifizierte Binärdarstellung von n (Formel in der unteren Seitenhälfte):
  • Hiermit läßt sich n = 0 nicht darstellen (dies sollte zumindest erwähnt werden, da die Informatik 0 gemeinhin zu den natürlichen Zahlen rechnet)
  • Ich halte es für nicht sehr gelungen, die Zählvariable i in einer Zeile mit zwei Bedeutungen zu belegen (zuerst von 0 bis l und dann von 0 bis l-1)
  • In der Zeile "aus den Endziffern [... a 3 3 ... 3] mit a \in {0,1,2} entsteht dabei die Ziffernfolge [... (a+1) 2 2 ... 2]" kann a die Werte 0 und 1 nur dann annehmen, wenn davor keine Werte mehr stehen. Dies geht aus der verwendeten Notation ("[ ... a") nicht klar hervor.
113 Theorem 3.5: "Die übrigen Kosten ändern sich der Größe nach nicht." Bezieht sich das auch auf die Kosten von extract(W,d)? Diese haben sich nämlich in Theorem 3.2 und 3.4 um einen logarithmischen Faktor erhöht; warum hier nicht?
(Daß es eine Operation "extract" geben muß, wird auf S. 113 oben deutlich.)
Die gleiche Frage stellt sich auf S. 117 oben: Warum lautet es "Extract(W,D,t) in Gesamtzeit O(E_V(n))"?
117 In Theorem 3.7 fehlt eine Laufzeitangabe zur Operation Extract(W, d).
119 2. Absatz: "Wir können jedem Knoten v eines 2-d-Baums..." (sonst macht die darauf folgende Bezeichnung "Rechteck R(v)" keinen Sinn)

Zurück zum Index

Kurseinheit 4

Seite: Fehler / Anmerkung:
152 Die Aussage "Weil alle Ecken aus der Eingabemenge S stammen, kann es insgesamt höchstens n Besuche geben" möchte ich anzweifeln, da z. B. die Punkte a und b aus Abbildung 4.7 nochmals besucht werden können. Ich würde 3 n als obere Schranke ansetzen, da insgesamt höchstens n Eckpunkte, die sofort danach aus der konvexen Hülle entfernt werden, besucht werden. Darüber hinaus besucht jeder eingefügte Punkt zwei Tangentialpunkte (die ja weiterhin in der konvexen Hülle verbleiben), was insgesamt höchstens 2 (n - 3) Besuche ausmacht. Die Gesamtzahl der Besuche ist also durch 3 n beschränkt. (Natürlich ändert dies nichts an der Laufzeitabschätzung).
168 Abschnitt "Höhle": "zur Konstruktion des Sichtbarkeitspolygons eignet sich diese Tatsache nicht" (nicht: "Sicherheitspolygons")
170 Letzter Absatz: Ich würde hier schreiben: "... wird der Durchlauf mit der ursprünglichen Drehrichtung fortgesetzt" (nicht: "wird die ursprüngliche Drehrichtung fortgesetzt").

Kommentar von Elmar Langetepe: Hierin sehe ich keinen Fehler; eine Änderung der Formulierung scheint mir daher nicht zwingend notwendig.

181 In der ersten Formel: "\alpha ( e_i, e_j )" oder "\alpha_{i,j}" (nicht: "\alpha ( i, j )" )
182 F und B sind hier in der Formel als Mengen dargestellt, der Text beschreibt sie aber als Folgen. Sie sollten also in der Formel mit runden Klammern notiert werden.
196 Der letzte Satz sollte vielleicht besser lauten: "Im letzten Fall entspricht die Anordnung der Punkte ... der Anordnung ihrer Voronoi-Regionen um x." (Der Begriff "Ordnung" hat die unterschiedlichsten Bedeutungen, und die "Ordnung eines Punktes" bzw. die "Ordnung einer Voronoi-Region" kann leicht mißinterpretiert werden (vgl. "Ordnung einer Davenport-Schinzel-Sequenz").)

Zurück zum Index

Kurseinheit 5

Seite: Fehler / Anmerkung:
227 Beweis zu Lemma 5.24: "Seien l_1 und l_2 zwei disjunkte Liniensegmente. Wenn beide auf derselben Geraden liegen, ist ihr Bisektor gleich dem Bisektor der benachbarten Endpunkte. Andernfalls schneiden sich ihre senkrechten Streifen."
Diesen Schluß finde ich voreilig. Die beiden Liniensegmente können durchaus auf zwei verschiedenen, zueinander parallelen Geraden liegen, ohne daß sich ihre senkrechten Streifen schneiden.

Zurück zum Index

Kurseinheit 6

Seite: Fehler / Anmerkung:
254 Letzter Satz vor 6.2.2: "... eine Lücke zur unteren Schranke von \Omega(n log n)" (nicht: "O(n log n)", denn es handelt sich um die untere Schranke)
256 Drittletzter Absatz: "denn außer der Wurzel und ihren vier Kindern werden ja nur solche [d. h. mit p_i in Konflikt stehende] Dreiecke besucht." Diese Aussage steht im Widerspruch zu der 2 Absätze weiter oben aufgeführten Beschreibung "Wir starten deshalb ... eine Tiefenerkundung und kehren jedesmal sofort um, wenn wir auf ein Dreieck stoßen, das mit p_i keinen Konflikt hat." Also werden auch andere, nicht mit p_i in Konflikt stehende Knoten besucht. Die Existenz solcher Knoten sollte wohl klar sein.
259 Mitte: Es wäre gut, ein paar erläuternde Worte zur Funktion "E()" anzubringen.
265 1. Absatz nach Lemma 6.11: "Die Wellenstücke in W sind also nach Y-Koordinaten geordnet." Woraus folgt das zu diesem Zeitpunkt?

Zurück zum Index

Kurseinheit 7

Seite: Fehler / Anmerkung:
291 2. Absatz: "... Modell der turtle, das schon in Abschnitt 4.2 auf Seite 164 erwähnt wurde." (nicht: "Abschnitt 4.4.1")
292 2. Absatz: "... vergleiche auch Abschnitt 4.2." (nicht: "Abschnitt 4.4.1")
305 Erster Absatz nach den Formeln: "Die für eine optimale Packung benötigte Anzahl m_opt von Behältern kann nicht kleiner sein." (Korrekterweise müßte es "höchstens größer oder gleich" heißen. Außerdem ist die ursprüngliche Formulierung "höchstens größer" sehr mathematisch und kann verwirrend wirken, da "höchstens" im normalen Sprachgebrauch auf eine Obergrenze hindeutet. Hier ist aber eine allgemeine Einschränkung gemeint.)
321 Im 2. Absatz des Beweises wäre folgende Formulierung hilfreich: "Wir machen es dem Roboter so schwer wie möglich und wählen das linke Polygon aus Abbildung 7.23, wenn er im Begriff ist, auf die linke Hälfte von h zu treffen..."
Die ursprüngliche Aussage "das linke" ist theoretisch ausreichend, aber wenn man sich intensiv in die Situation hineindenkt, kann man "das linke" auch auf "das Polygon mit der linken Ecke" oder "mit dem linken Kern" beziehen, was zu einer Vertauschung führt. Noch besser wäre vielleicht die Bezeichnung der Polygone mit Buchstaben und eine explizite Referenz auf "Polygon A" im Beweistext.

Kommentar von Elmar Langetepe: Hierin sehe ich keinen Fehler; eine Änderung der Formulierung scheint mir daher nicht zwingend notwendig.

Zurück zum Index