Discrete and Computational Geometry

by Satyan Devadoss and Joseph O'Rourke

Errata

Last Update:

Substantive Errors

Chap
Page
Location
Old
New
Explanation
Corrector
Date
1
7
Cor. 1.9
 has at least two ears. has at least two ears with non-adjacent tips. This stronger statement is needed for the induction step, and is used in the exercises.
Giovanni Viglietta
27 Jun 2011
1
11
Thm.1.20
 let P be any polygon with n labeled ordered vertices...let Q be a convex polygon also with n vertices let P be any polygon with n+2 labeled ordered vertices...let Q be a convex polygon also with n+2 vertices P and Q should have n+2 vertices.
Mario Lopez
6 Sep 2013
1
22
Ex. 1.48
 The claim in the exercise is false. Will delete or modify in 2nd Ed. Student found counterexample
Lori Ziegelmeier & Caleb Williams
9 Oct 2023
1
27-28
Line-2
 More precisely, let f : R → Q ... [to be written] Our attempt here to simplify Dehn's proof is incorrect. The function f should be defined on R / (π · Q), and we need to define a basis for the Q-linear vector space. We will be writing up a revsion of the proof. Meanwhile, consult Proofs from THE BOOK (Aigner, Ziegler), Chap. 7.
JOR & SLD
22 Nov 2011
1
30
Example 1.64
 could be the identity function on...= 3√2 f(arctan √2) could be the constant function 1 on ...= 3√2 The identity function fails to satisfy Property 1 on p.28.
JOR
6 Nov 2011
3
83
Thm. 3.49
 and A within and C outside the circle and A within and C outside the circle where A, B, C lie on the same side of the line through P and Q Assumption needed.
Chris Atkinson
27 Sep 2012
5
132,4
Figs. 5.12,14
 Bottom edge of R in 5.12, and top edge of -R in 5.14. Convolution curve is missing a loop at the upper reflex vertex. The topmost blue edge of -R in Fig.5.14 should have a larger slope so that it is steeper than the nearly parallel red edge incident to the top corner of P1. For a sketch of the repaired figure, see Fig5.14.jpg. The nearly parallel edges was an accident. The convolution should continue ccw cycling around -R until the outgoing P1 edge direction is reached.
Günter Rote
17 May 2011
5
137
Line+3
 The many convolution cycles in Figure 5.17 The many convolution loops in Figure 5.17 There is just one convolution cycle, which self-crosses in many "loops." As Günter points out, there can in fact be several convolution cycles that require new starting points to detect.
Günter Rote
17 May 2011
6
157
Exer. 6.2.
 Show that each face of a convex polyhedron must Show that each face of a convex polyhedron without coplanar faces must Temporary definition permits coplanar faces, but then could partition a convex face into nonconvex subfaces.
Giovanni Viglietta
12 Mar 2011
6
177
Thm. 6.35
 with corresponding faces congruent, then with corresponding faces congruent and similarly arranged around each vertex, then Here is an example of Connelly showing two incongruent polyhedra composed of congruent faces, but the correspondence between the two does not map the angles around each vertex identically.
NonCongruent
Robert Connelly
26 Aug 2011

Minor Errors: Typos, etc.

Chap
Page
Location
Old
New
Explanation
Corrector
Date
1
19
Line+2 of bottom para
 In 1992, Raimund Seidel constructed In 1982, Raimund Seidel and William Thurston independently constructed Typo on date; found 2nd reference.
Giovanni Viglietta; JOR
12 Mar 2011
1
12
Line-5
 in any of its triangulation. in any of its triangulations. Typo
Jennifer Sadler
14 Sep 2011
1
13
Exer. 1.26
 Should be starred.  ∗ Exercise 1.26. It is a hard exercise!
Giovanni Viglietta
27 Jun 2011
1
14
Exer. 1.28
 Are there are polygons Are there polygons Typo
Giovanni Viglietta; Justin Iwerks
27 Jun 2011
1
18
Thm. 1.38
 ⌈n/2⌉ guards are needed ⌈n/2⌉ boundary guards are needed (In contrast to Exer. 1.40's "anywhere in the plane.")
Giovanni Viglietta
27 Jun 2011
1
26
Line+8 of Sec. 1.5
 Max Dehn a few years later. Max Dehn within a year. The publication is: "Über den Rauminhalt", Mathematische Annalen 55 (1901), no. 3, pages 465–478.
Giovanni Viglietta
27 Jun 2011
1
26
Line+3 of Definition
 n1 . n2 = cos θ n1 . n2 = – cos θ The minus sign is needed because these are outward-pointing normals.
Giovanni Viglietta
27 Jun 2011
1
30
Line+1 after Thm 1.67
 This, along with the Dehn-Hadwiger theorem, show that This, along with the Dehn-Hadwiger theorem, shows that Grammar.
Giovanni Viglietta
27 Jun 2011
1
24,25, 252
several locations
 Bolyai-Gerwein Bolyai-Gerwien Spelling: ei vs. ie
SLD
17 Mar 2016
2
35
Part II, after 1st displayed equation
 conv(S') ⊂ conv(S) [twice] conv(S') ⊆conv(S) It could be that pn is in S'.
Giovanni Viglietta
27 Jun 2011
2
35
Fig. 2.5 caption.
 Tangent line lines transitioning Tangent line transitioning Typo
Giovanni Viglietta
27 Jun 2011
2
43
Line-3
 , which is n. , which is n-1. ~Typo. One point to all others.
Giovanni Viglietta
27 Jun 2011
2
43
Line+6
 makes the largest angle makes the smallest angle Typo
Lori Ziegelmeier
9 Oct 2023
2
51
Line+3 of Sec. 2.7
 a convex polyhedra a convex polyhedron Typo
Giovanni Viglietta
27 Jun 2011
2
53
Line+7
 all but one of them extends all but one of them extend Grammar
Giovanni Viglietta
27 Jun 2011
3
65
Uns. Prob. 11
 an exponential number of triangles an exponential number of triangulations Typo.
Dianna Xu
24 Feb 2013
3
60
Line-1 above box
 Notice that both ... affects Notice that both ... affect Grammar
Giovanni Viglietta
27 Jun 2011
3
69
Line+2 of para. before Cor. 3.24
 A quantity that give A quantity that gives Typo
Giovanni Viglietta
27 Jun 2011
3
68
Line-1
 which by our induction hypothesis which by our induction hypothesis establishes the theorem. Printing error (last three words of sentence missing).
Justin Iwerks
15 Aug 2011
3
75
2nd para., Line+9
 based on the six ways a hexagon may be cut into two quadrilaterals based on the three ways a hexagon may be cut into two quadrilaterals ~Typo
Justin Iwerks
15 Aug 2011
3
96
Unsolved Prob. 18, parenthetical sentence
 for all points sets for all point sets Typo
Justin Iwerks
19 Aug 2011
4
102
Line+3 after Exer. 4.8
 not all these bisectors becomes Voronoi edges not all these bisectors become Voronoi edges Typo
Justin Iwerks
27 Aug 2011
4
103
Proof of Theorem 4.12
 so the number of notes of G is n so the number of faces of G is n ~Typo
Uuganbaatar Ninjbat
2 Jan 2017
4
104
Line +2
 Substituting e = (v+1)+b-2 Substituting e = (v+1)+n-2 Typo
Uuganbaatar Ninjbat
3 Jan 2017
               
4
110
Theorem 4.26
   We should have mentioned explicitly that it is easy to construct Vor(S) from Del(S) and vice versa.  
Uuganbaatar Ninjbat
2 Jan 2017
4
115
Fig. 4.12 caption
 The point set in identical The point set is identical Typo
Justin Iwerks
27 Aug 2011
4
117
4th reference
 Otfried Schwartzkopf Otfried Cheong (He changed his name.)
Justin Iwerks
27 Aug 2011
5
133
Definition eqn for α * β
 x ∈ A, y ∈ B x ∈ α, y ∈ β Typo.
Dianna Xu
3 Nov 2015
6
181
Line-2
 ... + 6 f7 + ... ... + 6 f6 + ... Typo: f7 → f6
SLD
30 Mar 2016
7
207
Motion Planning Box heading
 Voronoi Diagram Algorithm Path Finding Algorithm ~Typo.
SLD
28 Feb 2011