Back to the index

Errata to the first edition

Following is a list of errata tot the first printing. Small typo's are not listed. Thanks to all readers who have contributed to this list. In particular, we would like to thank Matthew Katz and Nelson Max for sending extensive lists of errors and typo's.
1 Computational Geometry

2 Line Segment Intersection

3 Polygon Triangulation

4 Linear Programming

"exactly if vn lies in the interior of Cn-1" should be "exactly if vn lies in the interior of an edge of Cn-1"
p.79, l.7:
should be vn instead of xn
p.92, Ex 4.14:
"linear time algorithm" should be "algorithm with whose expected running time is linear"

5 Orthogonal Range Searching

p.96, l.6 of proof:
p<xvsplit should be p<=xvsplit

6 Point Location

p.137, 4th para, l.2/3:
Delete "the line through"
p.143, Ex 6.9:
"the order of points in x-direction" should be "the x-order of points with unequal x-coordinates".

7 Voronoi Diagrams

p.157, step 3 of HandleCircleEvent:
Not all that needs to be done to update the structures is mentioned. In particular, the Origin-field of the half-edges starting at the nes vertex must be set, end some more Next- and Prev-pointers must be set.

8 Arrangements and Duality

p. 175:
The argument in the 4th paragraph about the rightmost intersection not being unique is incorrect when the number of lines passing through the rightmost intersection is two. In this case the increase in the number of left bounding edges is five, because the "other" line through the intersection point also defines a left bounding edge that is split.

Moreover, the degenerate cases of parallel lines and several concurrent lines cannot be handled separately.

9 Delaunay Triangulations

p.196, l.28:
"Denote the subset of points in P that lie in a given triangle Delta by K(Delta)." This must, of course, be: "Denote the subset of points in P that lie in the circumcircle of a given triangle Delta by K(Delta)."
p.198, l.9:
"2m-1" should be "2m+1"
p.201, l.7:
"trapezoids" should read "configurations".

10 More Geometric Data Structures

In algorithm InsertSegmentTree, the two recursive calls in lines 4 and 6 should have as an argument "[x:x']" rather than "qx".
In figure 10.10, next to the top node, there should be "S(v1) = s3" rather than "S(v2) = s3".
The last two lines of exercise 10.4 must be removed; they don't make any sense.

11 Convex Hulls

At the 8th line from the bottom, in 2 ne <= 3 nf, the inequality shoud be reversed.
The formula in the third line of exercise 11.9 must be z=px x + py y - pz.

12 Binary Space Partitions

13 Robot Motion Planning

14 Quadtrees

In the one but last paragraph, replace the argument "(This follows for instance ... vertices.)" by "because each cell is subdivided in a constant number of triangles."

15 Visibility Graphs

16 Simplex Range Searching

The last sentence of the proof is only valid because the degree of the internal nodes of the tree is at least two.
At the last line of the first paragraph we refer to two lemmas. Don't try to find the second one; it does not exist.