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.
- 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.
- 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)logc n)
for a suitable constant c, not to O(sqrt(n)logn).