Errata for the book Geometric Spanner Networks

• Page 8: The Gilbert-Pollak conjecture has not been proved yet; see
  
  
  • N. Innami, B. H. Kim, Y. Mashiko, and K. Shiohama. The Steiner ratio conjecture of Gilbert-Pollak may still be open. Algorithmica, volume 57, 2010, pages 869-872.
    
    
  • A. O. Ivanov and A. A. Tuzhilin. The Steiner ratio Gilbert-Pollak conjecture is still open (clarification statement). Algorithmica, volume 62, 2012, pages 630-632.
  
  
  
• 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 14: In Exercise 1.14, assume that the closest-pair distance in S is at least 1. The size of the spanner thus depends on the spread of S, which is the ratio of the diameter and the closest-pair distance. (Reported by Sander Verdonschot on November 1, 2011.)
  
  
• Page 18: In the quote, replace "Gell-mann" by "Gell-Mann".
  
  
• Page 25: In Lemma 2.3.3, replace "Let k be the integer" by "Let k be an integer".
  
  
• Page 63: In the second line after the quote, replace "higways" by "highways". (Reported by Simon Pratt on May 25, 2012.)
  
  
• Page 66: In algorithm Theta-Walk(p,q), p_{i+1} should be the point in the cone C_{p_i} whose orthogonal projection is closest to p_i; thus, the edge {p_i,p_{i+1}} is in the Theta-graph, because p_i chooses it. Since the Theta-graph is an undirected graph, there may be a very long edge {p_i,r} such that r is also in the cone C_{p_i}; this edge is in the graph, because r chooses it. Algorithm Theta-Walk(p,q) should not use the edge {p_i,r} to walk from p to q. (Reported by Paz Carmi on March 30, 2009.)
  
  
• Page 77: 4 lines above Theorem 4.2.5, replace "Since each edge" by "Since each vertex". (Reported by Paz Carmi on April 11, 2009.)
  
  
• Page 91: The geographic neighborhood graph (also known as the Yao graph) was discovered independently by B. E. Flinchbaugh and L. K. Jones (Strong connectivity in directional nearest-neighbor graphs, SIAM Journal on Algebraic and Discrete Methods, 1981, volume 2, pages 461-463).
  
  
• Page 102: in the pseudocode, replace "associated structure of r" by "associated structure of w". (Reported by Gregory Bint on October 9, 2012.)
  
  
• Page 110: just above (6.1), replace "lemma" by "theorem". (Reported by Gregory Bint on November 23, 2012.)
  
  
• Page 113: In line 8, replace "E_S" by "E_s". (Reported by Mohammad Farshi on February 2, 2013.)
  
  
• Page 118: In Exercise 6.1, replace "let S be finite set" by "let S be a finite set".
  
  
• 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 176: In the middle of this page, it is mentioned that the balanced aspect ratio tree can be used to obtain a WSPD. The number of pairs in this WSPD, however, cannot be linear in the worst case. This follows from Theorem 5.3 in Callahan and Kosaraju (Journal of the ACM, volume 42, 1995, pages 67-90), which states the following: There exists a set S of n points in R^d, such that any binary tree that results in a WSPD with O(n) pairs must have height Omega(n^{epsilon}). Observe that the balanced aspect ratio tree has height O(log n). (Reported by Mohammad Farshi on August 22, 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 207: In the second sentence of Section 11.6: k = O(s^d (1 + gamma s)^d log(1/beta)).
  
  
• Page 213: In Lemma 11.8.2, replace "Let be $p$ be" by "Let $p$ be".
  
  
• Page 225: The proof of Lemma 12.1.6 is wrong. Here is a correct proof. (Reported by Shay Solomon on July 11, 2010.)
  
  
• Page 240 (and Open Problem 20 on page 481): The statement in the first open problem on page 240 is obviously wrong for large values of k. For example, if k = 2 + 2 alpha(n), then alpha_k(n) is a constant (by Lemma 12.1.22). For this value of k, the statement contradicts the fourth claim in Theorem 12.2.1. (Reported by Shay Solomon on October 7, 2008.)
  
  
• Page 253: In line 7 of Exercise 13.3, replace "B_1" by "B_i".
  
  
• Page 261: On February 2, 2013, Mohammad Farshi informed us that Abolfazl Poureidi found an error in the proof of Lemma 14.3.1. It turns out that the lemma is, in fact, wrong. This document
  
  
  • gives a counter example,
    
    
  • shows that the lemma is true for strong spanners,
    
    
  • shows that the lemma is true for the generalized leapfrog property,
    
    
  • shows the correct version of Lemma 15.2.15 on page 350.
    
    
  Because of this, the following changes have to be made:
  
  
  • Page 261: The graph G must be a strong t-spanner for S.
    
    
  • Page 326: Replace the sentence just above Lemma 15.1.10 by "Since the path-greedy spanner is a strong spanner, Lemmas 15.1.9 and 14.3.1 immediately imply the following result:"
    
    
  • Page 327, line -6: (sqrt{tt'},t sqrt{tt'})-leapfrog
    
    
  • Middle of page 330: (t',tt')-leapfrog
    
    
  • Top of page 347: (t',tt')-leapfrog
    
    
  • Bottom of page 349: (t',tt')-leapfrog
    
    
  • Page 350, Lemma 15.2.15: (t',tt')-leapfrog
    
    
  • Page 350, just above Theorem 15.2.16: $1 < 1 - \phi + \phi tt' < t' < tt'$
    
    
  • Page 350, in Theorem 15.2.16: $1 < 1 - \phi + \phi tt' < t' < tt'$
    
    
  • Page 350, in item 3 of Theorem 15.2.16: Replace (1/(t-1))^{2d} by (1/(tt'-1))^{2d}.
    
    
  • Page 352, line 10: we take $t'$ slightly larger than $(1 - \phi) / (1 - \phi t)$, so that $1 < 1 - \phi + \phi tt' < t' < tt'$.
    
    In the next few lines: If $t = 1 + \epsilon$, then $\sqrt{t} \sim 1 + \epsilon/2$, $t' \sim 1 + c_1 \epsilon$, $\sqrt{t'} \sim 1 + c_1 \epsilon/2$, $\sqrt{t/t'} \sim 1 + c_2 \epsilon$, $\alpha \sim c_3 \epsilon$, for some constants $c_1$, $c_2$, and $c_3$.
    
    
  • Page 352, line 5 of Remark 15.2.18: Replace (1/(t-1))^{2} by (1/(t-1))^{2d}.
    
    
  • Page 354: (t',tt')-leapfrog
    
    
  • Last line of page 374, : (t',tt')-leapfrog
    
    
  • Twice at the bottom of page 378: (t',tt')-leapfrog
    
    
  • Twice at the bottom of page 378: $1 < 1 - \phi + \phi tt' < t' < tt'$
    
    
  • Page 379, in item 3 of Theorem 15.3.19: Replace (1/(t-1))^{2d} by (1/(tt'-1))^{2d}.
    
    
  • Bottom of page 380: we take $t'$ slightly larger than $(1 - \phi) / (1 - \phi t)$, so that $1 < 1 - \phi + \phi tt' < t' < tt'$.
    
    In the next few lines: If $t = 1 + \epsilon'$, then $\sqrt{t} \sim 1 + \epsilon'/2$, $t' \sim 1 + c_1 \epsilon'$, $\sqrt{t'} \sim 1 + c_1 \epsilon'/2$, $\sqrt{t/t'} \sim 1 + c_2 \epsilon'$, $\alpha \sim c_3 \epsilon'$, for some constants $c_1$, $c_2$, and $c_3$.
  
  
  
• Page 387: The end-of-proof sign belongs after the third line of the proof.
  
  
• Page 460: According to footnote 7 on page 13 in S. Kisfaludi-Bak, J. Nederlof, and K. Wegrzycki, A Gap-ETH-tight approximation scheme for Euclidean TSP, version 3, posted on September 11, 2024, the swapping of the indices i and j in the summations is incorrect. They propose a method to fix this.
  
  
• Page 474: Replace the first paragraph by
  
  Given a set S of n points in R^d, Eppstein and Wortman [2005] 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 480: In Open Problem 13, replace "IT^d" by "R^d".
  
  
• Page 488: In the reference Govindarajan et al., delete "[See notes]".
  
  
• Page 493: The correct title of Talwar's paper is "Bypassing the embedding: algorithms for low dimensional metrics".
  
  
• Page 494: The correct title of Yao's 1991-paper is "Lower bounds for algebraic computation trees of functions with finite domains".