**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
*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**-

- 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 *v*_{n+2} = v_{2} and
and *w*_{n+2} = w_{2}.

**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**-