## Errata for the book Geometric Spanner Networks

• Page 10: The spanners for US cities are in the wrong order. The caption should read: "Six geometric \$t\$-spanner networks on 532 US cities with stretch factors of (a) \$10\$, (d) \$5\$, (c) \$3\$, (e) \$2\$, (b) \$1.5\$, and (f) \$1.2\$, respectively." (Reported by Neil Rhodes on March 15, 2007.)

• Page 18: In the quote, replace "Gell-mann" by "Gell-Mann".

• Page 166: In line 4 of the proof of Lemma 9.4.4, replace "R(pi(b)" by "R(pi(b))". In line 6 of the same proof, replace "R(pi(a)" by "R(pi(a))". (Reported by Mohammad Farshi on October 16, 2007.)

• Page 174: In Theorem 9.6.2, replace the two occurrences of "n/s^{O(lambda)}" by "s^{O(lambda)} n". (Reported by Mohammad Farshi on February 5, 2008.)

• Page 177: In line -11, replace "ration" by "ratio".

• Page 177: Replace the sentence starting in line -8 by "They showed how to construct in \$O(n \log n)\$ expected time a hierarchical net for doubling metrics."

• Page 480: In Open Problem 13, replace "IT^d" by "R^d".

• Page 474: Replace the first paragraph by

Given a set S of n points in R^d, Eppstein and Wortman  considered the problem of computing the ``star graph'' with the least stretch factor. A star graph has exactly one internal vertex called its center with edges from the center to every other vertex; it has no other edges. Eppstein and Wortman considered two versions of the problem. In the first version, the center can be any point in R^d; thus, the main problem is finding the location of the ``best'' center. In the second version, the center must be a point of S; thus, the main problem is that of identifying the star with the least stretch factor among the n possible star graphs. Both versions of this problem have applications to various versions of the facility location problem.

• Page 494: The correct title of Yao's 1991-paper is "Lower bounds for algebraic computation trees of functions with finite domains".