Back to the index

Errata to the first edition

1 Computational Geometry

2 Line Segment Intersection

3 Polygon Triangulation

4 Linear Programming

p.78/79:

"exactly if v_n lies in the interior of C_n-1" should be "exactly if v_n lies in the interior of an edge of C_n-1"

p.79, l.7:

should be v_n instead of x_n

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<x_vsplit should be p<=x_vsplit

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+₁"

p.201, l.7:

"trapezoids" should read "configurations".

10 More Geometric Data Structures

p.225:

In algorithm InsertSegmentTree, the two recursive calls in lines 4 and 6 should have as an argument "[x:x']" rather than "q_x".

p.226:

In figure 10.10, next to the top node, there should be "S(v₁) = s₃" rather than "S(v₂) = s₃".

p.229:

The last two lines of exercise 10.4 must be removed; they don't make any sense.

11 Convex Hulls

p.235:

At the 8th line from the bottom, in 2 n_e <= 3 n_f, the inequality shoud be reversed.

p.248:

The formula in the third line of exercise 11.9 must be z=p_x x + p_y y - p_z.

12 Binary Space Partitions

13 Robot Motion Planning

14 Quadtrees

p.300:

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

p.325:

The last sentence of the proof is only valid because the degree of the internal nodes of the tree is at least two.

p.333:

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.