Go up to Top

Errata to the second edition

Following is a list of errata for the second edition. Thanks to all readers who have contributed to this list.

Preface

1 Computational Geometry

2 Line Segment Intersection

3 Polygon Triangulation

4 Linear Programming

p.89: In the proof of Theorem 4.15, the sentence between brackets ius incorrect.
p.93: In Exercise 4.10, the common intersection of the half-planes in H should be non-empty and their boundaries should not all be parallel.

5 Orthogonal Range Searching

6 Point Location

7 Voronoi Diagrams

8 Arrangements and Duality

9 Delaunay Triangulations

p.190: In Theorem 9.6(i) the p_r in line 2 should be p_k.
p.196, l.9: "One the one hand" should be "On the one hand".
p.196: Due to the way the special points p_-1, p_-2, and p_-3 are chosen and handled, the Delaunay triangulation computed by the algorithm need not always be planar when embedded as a straigh-line graph: the edges incident to the special points could intersect the `real' edges. This is not a problem (the special points and their incident edges will be deleted at the end of the algorithm anyway), and the algorithm is still correct, but it is perhaps a little confusing.
p.208: In Exercise 9.5(a), one has to assume that the points p,q,r are oriented counterclockwise, otherwise the determinant should be negative instead of positive.
p.209: In part (b) of Exercise 9.13, the second p should be P.

10 More Geometric Data Structures

11 Convex Hulls

12 Binary Space Partitions

13 Robot Motion Planning

p.279: The code of Algorithm MinkowskiSum is not completely correct: one has to be careful that i and j do not get incremented beyond n+1 resp. m+1. Alternatively, we may define v_n+2 = v₂ and and w_n+2 = w₂.

14 Quadtrees

15 Visibility Graphs

16 Simplex Range Searching

p.338: The bound stated in Exercise 16.6 is not correct: the query time reduces to O(sqrt(n)log^c n) for a suitable constant c, not to O(sqrt(n)logn).

Bibliography