| 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"). |
| 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. |
| 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):
|
| 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) |
| 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").) |
| 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. |
| 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? |
| 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. |