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

• p.181: In Exercise 8.3, the word "faces" in the second line should be "edges".
• p.182: Exercise 8.13 seems to be rather tricky ...

9 Delaunay Triangulations

• p.190: In Theorem 9.6(i) the pr in line 2 should be pk.
• 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

• p.249: An n is missing behind the second log on line 8.

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 vn+2 = v2 and and wn+2 = w2.