Progress on open problems in the book Geometric Spanner Networks

• Open Problem 3 (page 471) What is the smallest real number t, such that a plane t-spanner exists for every finite set of points in the plane?
  
  Chew [1989] has shown that a plane 2-spanner exists for every set of points in the plane. It is clear that every plane graph on the four vertices of a square has stretch factor at least sqrt(2).
  
  
  • Wolfgang Mulzer (Minimum dilation triangulations for the regular $n$-gon. Master's Thesis, Freie Universit{\"a}t Berlin, 2004) has shown that every plane graph whose vertices are the corners of a regular 21-gon has stretch factor at least 1.41611 (which is larger than sqrt(2)).
  
  
  
• Open Problem 4 (page 472) What is the smallest integer D, such that, for some real number t that depends only on D, a plane t-spanner of maximum degree at most D exists, for every finite set of points in R^2?
  
  
  • I. A. Kanj and L. Perkovic (On geometric spanners of Euclidean and unit disk graphs, Proceedings of the 25th Symposium on Theoretical Aspects of Computer Science, 2008, pages 409-420) prove the following:
    
    Assume the Delaunay triangulation DT of a set S of n points in the plane is given. In O(n) time, a subgraph of DT can be computed whose maximum degree is at most 14 and which is a t-spanner of S (for some constant t).
    
    
• Open Problem 8 (page 474) For a given positive integer k, define a k-star as a graph with k internal vertices called hubs, edges from the hubs to all other vertices, and with no other edges in the graph. Given a set of points in R^d, design an algorithm to identify the k-star with the smallest stretch factor.
  
  
  • Augustine, Eppstein, and Wortman (Approximate weighted farthest neighbors and minimum dilation stars) prove the following:
    
    For k=1 and in any constant dimension, if the hub must be one of the input points, then a (1+epsilon)-approximation to the minimum-dilation star can be computed in O(n log n) expected time.
  
  
  
• Open Problem 10 (page 478) For which classes of graphs does there exist a polynomial-time algorithm that, when given a set S of n points in R^d, computes a graph in this class whose vertex set is S and whose stretch factor is minimum?
  
  
  • P. Giannopoulos, C. Knauer, and D. Marx (Minimum-dilation tour is NP-hard, Proceedings of the 23rd European Workshop on Computational Geometry, 2007, pages 18-21) have shown that the following two problems are NP-hard:
    
    Given a set S of points in the plane and a parameter t>1, decide if there exists a Hamilton cycle on P with stretch factor at most t.
    
    Given a set S of points in the plane and a parameter t>1, decide if there exists a Hamilton path on P with stretch factor at most t.
  
  
  
• Open Problem 11 (page 479) Is it possible to compute spanners in o(n log n) time, if the floor function, indirect-addressing, and/or randomization are added to the algebraic computation-tree model?
  
  
  • Mihai Pătraşcu and Timothy Chan (Voronoi diagrams in n times 2^{O(sqrt(lglg n))} time, Proceedings of the 39th ACM Symposium on the Theory of Computing, 2007, pages 31-39) prove the following:
    
    Given n points in the plane with integer coordinates bounded by 2^w, the Voronoi diagram can be constructed in n times 2^{O(sqrt(lglg n))} expected time by a randomized algorithm on the unit-cost RAM with word size w. The Delaunay triangulation has a bounded stretch factor and can be computed within the same time bound.
  
  
  
• Open Problem 12 (page 480) Construct spanners that can be maintained under insertions and deletions of points, in o(n) worst-case or amortized time per update.
  
  
  • Liam Roditty (Fully dynamic geometric spanners, Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007, pages 373-380) proves the following:
    
    For every set of n points in d-dimensional space, there exists a (1+eps)-spanner with O(n/eps^d) edges, which can be maintained in O(log n) amortized time per insertion and O(n^{1/3} polylog(n)) amortized time per deletion.
    
    
  • Lee-Ad Gottlieb and Liam Roditty (Improved algorithms for fully dynamic geometric spanners and geometric routing, Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms, 2008, pp. 591-600) prove the following:
    
    For every set of n points in d-dimensional space, there exists a (1+eps)-spanner which can be maintained under insertions and deletions of points, in O(log^3 n) amortized time per operation.
  
  
  
• Open Problems 20 and 21 (page 481)
  • Let t>1 be a real constant, and let k>2 be an integer. Prove that there exists a set S of n points in R^d, such that every t-spanner for S, whose spanner diameter is less than or equal to k, contains Omega(k n alpha_k(n)) edges.
  • Let t>1 be a real constant. Prove that there exists a set S of n points in R^d, such that every t-spanner for S, which consists of O(n) edges, has spanner diameter Omega(alpha(n)).
  
  
  • T-H. Hubert Chan and Anupam Gupta (Small hop-diameter sparse spanners for doubling metrics, Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, 2006, pages 70-78) solve both these problems on the real line.