This document provides a list of errata for the second edition of a computational geometry textbook. It contains over 50 corrections to various pages and figures across 14 chapters. The errata include fixes to text, equations, figures, code samples, theorems, examples and exercises. The corrections cover topics like line segment intersection, polygon triangulation, Voronoi diagrams, convex hulls, visibility graphs and more.
This document provides a list of errata for the second edition of a computational geometry textbook. It contains over 50 corrections to various pages and figures across 14 chapters. The errata include fixes to text, equations, figures, code samples, theorems, examples and exercises. The corrections cover topics like line segment intersection, polygon triangulation, Voronoi diagrams, convex hulls, visibility graphs and more.
This document provides a list of errata for the second edition of a computational geometry textbook. It contains over 50 corrections to various pages and figures across 14 chapters. The errata include fixes to text, equations, figures, code samples, theorems, examples and exercises. The corrections cover topics like line segment intersection, polygon triangulation, Voronoi diagrams, convex hulls, visibility graphs and more.
This document provides a list of errata for the second edition of a computational geometry textbook. It contains over 50 corrections to various pages and figures across 14 chapters. The errata include fixes to text, equations, figures, code samples, theorems, examples and exercises. The corrections cover topics like line segment intersection, polygon triangulation, Voronoi diagrams, convex hulls, visibility graphs and more.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
You are on page 1/ 4
Errata to the second edition
February 14, 2008
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
• p.13, l.-9: Hersberger should be Hershberger.
• p.16, exercise 1.7: ”Now imagine that we start with a vertical line and rotate . . .” should be ”Now imagine that we start with a vertical line through p1 and rotate . . .”
2 Line Segment Intersection
• p.34, mid: ”This suggest the following approach.” An ”s” is missing.
• p.40, fig. 2.7: The little triangle at the top right inside P1 should be shaded as well. • p.42, l.-4: ”incident” should be ”adjacent”. • p.43, l.-12: ”...it must be is impossible...” Remove ”is”.
3 Polygon Triangulation
• p.47, l.11: ”...let v 0 be the farthest from uv.” This should be: ”...let v 0 be the farthest from the line supporting uv.” • p.51, l.-5: ”are stored in an event queue”. • p.52, mid: ”Let ej and ek be the edges immediately to the right and to the left”; left and right should be exchanged. • p.55, l.5: A space is missing before HandleEndVertex. • p.58, mid: Add a space between ”theorem” and ”3.6”.
4 Linear Programming
1 • p.70, l.-9: ”...or its is...”. Remove an ”s”. • p.85, l.-7: ”Then algorithm...” Remove the ”n”. • p.89, l.-10: The sentence between brackets is 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
• p.105, mid: ”Kd-trees can be also be ...”. Remove a ”be”.
• p.106, in bulleted list: ”coordinate” should be ”coordinates” (twice). • p.107, l.-3: ”y-coordinate” should be ”y-coordinates”.
6 Point Location
7 Voronoi Diagrams
• p.156, top margin figure: The two unlabeled points also define arcs on the beach line far to the left and right. Hence, the tree is not complete.
8 Arrangements and Duality
• p.171, mid: ”This means that in dual” should be ”This means that in the dual”. • p.174, l.16: ”If `i is a vertical line we can locate the bottom intersection point of `i and Ai to start off the traversal.” This should have been Ai−1 . • p.181: In Exercise 8.3, the word ”faces” in the second line should be ”edges”.
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: Technicalities with the special points p−1 , p−2 and p−3 are treated better in the third edition. This chapter from the third edition can be downloaded from the web page of the book. • p.202, top margin figure: Enlarge. • p.206, mid: The last part of the equation contains = but it should be ≤. • p.208: In Exercise 9.5(a), one has to assume that the points p, q, r are oriented clockwise (in a right-handed system), otherwise the determinant should be negative instead of positive. • p.208: In Exercise 9.8, ”that contains p.” should be ”that contains q.”.
2 • p.209: In Exercise 9.12, we want to ask for an approximation factor of 2, not of 3/2, or else you need matching and not just the EMST. • p.209: In part (a) of Exercise 9.13, we should assume that for any two points p, q, if the smallest enclosing circle does not contain other points of P inside, then it also does not contain points of P on the boundary. • p.209: In part (b) of Exercise 9.13, the second p should be P . • p.210: In part (a) of Exercise 9.16, there should be a space between Pi , and q. Also, pi pj should be pq.
10 More Geometric Data Structures
• p.213, l-8: p. 213: ”we image the real line” should be ”we consider the real line”. p.217, l.7: ”top” should be ”bottom” for consistency with the text on page 213. • p.224, l.-11: ”the” is missing. • p.233: In Exercise 10.11, the lc(ν) and rc(ν) should be lc(νsplit ) and rc(νsplit ) • p.233: In Exercise 10.12, a space is missing in the first line.
11 Convex Hulls
• p.247, l.-4: q(p) should be q(r).
• p.247, l.-3: h(p) should be q(p). • p.249, l.8: An n is missing behind the second log. • p.249, ex. 11.2: The bounds asked for are wrong. They should be O(n3 ) and Θ(n3 ).
12 Binary Space Partitions
• p.261, l.12: ”I \ {sk }” should be ”I \ {sk−1 }”
13 Robot Motion Planning
• p.268, l.-9: ”the” is missing before ”origin”.
• p.268, l-5: ”rotated clockwise” should be ”rotated counterclockwise”. • p.277, l.3,4: The definition given here is for convex objects only. For non-convex objects, one should add the condition that o1 ∩ o2 is connected. An alternative definition is that the part of the boundary of o1 in the interior of o2 is connected, and vice versa. Also, the definition of proper intersection (l.9) only applies to convex objects. • p.277, mid: Observation 13.6 is valid for convex pseudodiscs only, see the comment above. • 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 .
3 14 Quadtrees
15 Visibility Graphs
• p.315, mid: The O(n2 ) bound for shortest paths has been improved to O(n log n) by Hershberger and Suri.
16 Simplex Range Searching
• p.338: √ The bound stated in Exercise 16.6 is not√ correct: the query time reduces to O( n logc n) for a suitable constant c, not to O( n log n).
Bibliography
• p.341, l.1: ”Schwarzkopf” is completely miswritten.
Watch and Clock Escapements
A Complete Study in Theory and Practice of the Lever, Cylinder and Chronometer Escapements, Together with a Brief Account of the Origin and Evolution of the Escapement in Horology
Watch and Clock Escapements
A Complete Study in Theory and Practice of the Lever, Cylinder and Chronometer Escapements, Together with a Brief Account of the Origin and Evolution of the Escapement in Horology
