Progress on open problems in the book Geometric Spanner Networks

• Open Problem 2 (page 470) Prove that, for every set S of points in the plane, the Delaunay triangulation of S is a $(\pi/2)$-spanner.
  
  
  • P. Bose, L. Devroye, M. L\"offler, J. Snoeyink, and V. Verma (Almost all Delaunay triangulations have stretch factor greater than $\pi/2$, Computational Geometry: Theory and Applications, volume 44, 2011, pages 121-127) have shown that this claim is not true:
    
    
    • There exists a set of points whose Delaunay triangulation has stretch factor at least 1.5846.
    • There exists a set of points in convex position whose Delaunay triangulation has stretch factor at least 1.5810.
  
  
  • G. Xia and L. Zhang (Improved lower bound for the stretch factor of Delaunay triangulations, 20th Annual Fall Workshop on Computational Geometry, 2010) have shown the following:
    
    
    • There exists a set of points whose Delaunay triangulation has stretch factor at least 1.5907.
  
  
  • G. Xia and L. Zhang (Toward the tight bound of the stretch factor of Delaunay triangulations, Proceedings of the 23rd Canadian Conference on Computational Geometry, 2011, pages 175-180) have shown the following:
    
    
    • There exists a set of points whose Delaunay triangulation has stretch factor at least 1.5932.
  
  
  • S. Cui, I. A. Kanj, and G. Xia (On the stretch factor of Delaunay triangulations of points in convex position, Computational Geometry: Theory and Applications, volume 44, 2011, pages 104-109) have shown the following:
    
    
    • The Delaunay triangulation of every point set in convex position has stretch factor at most 2.33.
  
  
  • G. Xia (The stretch factor of the Delaunay triangulation is less than 1.998, SIAM Journal on Computing, volume 42, 2013, pages 1620-1659) has shown the following:
    
    
    • The Delaunay triangulation of every point set has stretch factor less than 1.998.
  
  
  • X. Tan, C. Sakthip, and B. Jiang (Improved stretch factor of Delaunay triangulations of points in convex position, COCOA 2019, LNCS 11949, pages 473–484) have shown the following:
    
    
    • The Delaunay triangulation of every point set in convex position has stretch factor at most 1.83.
  
  
  
• 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).
  
  
  • W. 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)).
  
  
  • A. Dumitrescu and A. Ghosh (Lower bounds on the dilation of plane spanners) have shown that every plane graph whose vertices are the corners of a regular 23-gon has stretch factor at least 1.4308.
  
  
  • G. Xia (The stretch factor of the Delaunay triangulation is less than 1.998, SIAM Journal on Computing, volume 42, 2013, pages 1620-1659) has shown that the Delaunay triangulation of every point set has stretch factor less than 1.998.
  
  
  • M. Amani, A. Biniaz, P. Bose, J.-L. De Carufel, A. Maheshwari, and M. Smid (A plane 1.88-spanner for points in convex position, Journal of Computational Geometry, volume 7(1), 2016, pages 520-539) have shown the following: For every point set in convex position, there exists a plane 1.88-spanner.
  
  
  
• 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, L. Perkovic, and G. Xia (On spanners and lightweight spanners of geometric graphs, SIAM Journal on Computing, volume 39, 2010, pages 2132-2161) 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).
    
    
  • I. A. Kanj and G. Xia (Improved local algorithms for spanner construction, Theoretical Computer Science, volume 453, 2012, pages 54-64) 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 11 and which is a t-spanner of S (for some constant t).
    
    
  • P. Bose, P. Carmi, and L. Chaitman-Yerushalmi (On bounded degree plane strong geometric spanners, Journal of Discrete Algorithms, volume 15, 2012, pages 16-31) prove the following:
    
    The Delaunay triangulation of a set of n points in the plane contains a subgraph whose maximum degree is at most 7 and which is a t-spanner of S (for some constant t). This subgraph can be computed in O(n log n) time.
    
    For every set of n points in the plane, there exists a plane t-spanner (for some constant t) of maximum degree 6; it can be computed in O(n log n) time. Note: this spanner is not a subgraph of the Euclidean Delaunay triangulation. Note: F. Anderson, A. Ghosh, M. Graham, L. Mougeot, and D. Wisnosky, Bounded-degree plane geometric spanners in practice give an example of a point set for which the algorithm constructs a plane spanner of maximum degree 7.
    
    
  • N. Bonichon, C. Gavoille, N. Hanusse, and L. Perkovic (Plane spanners of maximum degree six, Proceedings of the 37th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, volume 6198, Springer-Verlag, Berlin, 2010, pages 19-30) prove the following:
    
    For every set of n points in the plane, there exists a plane 6-spanner of maximum degree 6; it can be computed in O(n log n) time. Note: this spanner is not a subgraph of the Euclidean Delaunay triangulation.
    
    
  • N. Bonichon, I. Kanj, L. Perkovic, and G. Xia (There are plane spanners of degree 4 and moderate stretch factor, Discrete & Computational Geometry, volume 53, 2015, pages 514-546) prove the following:
    
    For every finite set of points in the plane, there exists a plane spanner of maximum degree 4. Note: this spanner is not a subgraph of the Euclidean Delaunay triangulation.
    
    
  • I. Kanj, L. Perkovic, and D. Turkoglu (Degree four plane spanners: simpler and better) construct a plane 20-spanner of maximum degree 4. This spanner is not a subgraph of the Euclidean Delaunay triangulation.
  
  
  
• 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.
  
  
  • J. Augustine, D. Eppstein, and K. A. Wortman. (Approximate weighted farthest neighbors and minimum dilation stars, Proceedings of the 16th Annual International Computing and Combinatorics Conference, Lecture Notes in Computer Science, volume 6196, Springer-Verlag, Berlin, 2010, pages 90-99) 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 9 (page 474) Given a geometric graph G with n vertices and m edges, and given a positive integer k, add k edges to G such that the stretch factor of the resulting geometric graph is minimized (or approximately minimized).
  
  
  • C. Wulff-Nilsen (Computing the dilation of edge-augmented graphs in metric spaces, Computational Geometry: Theory and Applications, volume 43, 2010, pages 68-72) has shown the following:
    
    For k=1, such an edge can be computed in O(n^3 log n) time using O(n^2) space.
    
    
  • J. Luo and C. Wulff-Nilsen (Computing best and worst shortcuts of graphs embedded in metric spaces, Proceedings of the 19th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, volume 5369, Springer-Verlag, Berlin, 2008, pages 764-775) have shown the following:
    
    For k=1, such an edge can be computed in O((n^4 log n) / sqrt{m}) time using O(m+n) space.
    
    
  • J. Gudmundsson and S. Wong (Improving the dilation of a metric graph by adding edges) have shown the following:
    
    For k>1, in O(n^3 log n) time, k edges can be computed, whose addition to G results in a graph whose stretch factor is within O(k) of the minimum stretch factor.
  
  
  
• 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, R. Klein, C. Knauer, M. Kutz, and D. Marx (Computing geometric minimum-dilation graphs is NP-hard, International Journal of Computational Geometry & Applications, volume 20, 2010, pages 147-173) have shown that the following problems are NP-hard:
    
    Given a set S of points in the plane and parameters t>1 and K, decide if there exists a graph with vertex set S and at most K edges, whose stretch factor is at most t.
    
    Given a set S of points in the plane and a parameter t>1, decide if there exists a plane graph with vertex set S whose stretch factor is at most t.
    
    Given a set S of points in the plane and a parameter t>1, decide if there exists a Hamilton cycle on S 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 S with stretch factor at most t.
    
    
  • A. Khopkar and S. Govindarajan (Hardness results for computing optimal locally Gabriel graphs, Proceedings of the 24th Canadian Conference on Computational Geometry, 2012, pages 149-154) have shown that the following problem is NP-hard:
    
    Given a set S of points in the plane, decide if there exists a Locally Gabriel Graph with vertex set S whose stretch factor is at most 7.
    
    
  • O. Cheong and C. Lee (Single-source dilation-bounded minimum spanning trees) have shown that the following problem is NP-hard:
    
    Given a set S of points in the plane, a point r of S, and numbers L and t, decide if there exists a spanning tree of S whose weight is at most L and for which, for each point p of S, the stretch factor between r and p is at most t.
    
    
  • P. Carmi and L. Chaitman-Yerushalmi (Minimum weight Euclidean t-spanner is NP-hard) have shown that the following problems are NP-hard:
    
    Let t>1 be a constant. Given a set S of points in the plane and a parameter w>0, decide if there exists a t-spanner for S whose weight is at most w.
    
    Let t>1 be a constant. Given a set S of points in the plane and a parameter w>0, decide if there exists a plane t-spanner for S whose weight is at most w.
    
    
  
  
  
• 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.
    
    
  • T. M. Chan (Well-separated pair decomposition in linear time?, Information Processing Letters, volume 107, 2008, pages 138-141) proves the following:
    
    If the spread of the point set is polynomial, and if the floor function is available as a unit-time operation, then the WSPD can be computed in O(n) time. Thus, for this case, (1+eps)-spanners can be computed in O(n) time.
  
  
  
• 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, Algorithmica, volume 62, 2012, pages 1073-1087) 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, pages 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.
    
    
  • Lee-Ad Gottlieb and Liam Roditty (An optimal dynamic spanner for doubling metric spaces, Proceedings of the 16th European Symposium on Algorithms, Lecture Notes in Computer Science, volume 5193, Springer-Verlag, Berlin, 2008, pages 478-489) prove the following:
    
    For every set of n points in a metric space of bounded doubling dimension, there exists a (1+eps)-spanner whose maximum degree is O(1) and which can be maintained under insertions and deletions of points, in O(log n) time per operation.
  
  
  
• Open Problem 13 (page 480) Let $d \geq 2$ be an integer constant. For a given real number t>1, prove a lower bound of $\Omega(n log n)$ time in the algebraic computation-tree model for the problem of computing a Steiner t-spanner for a given set S of n points in R^d in general position.
  
  This problem was solved in M. Farshi and A. Poureidi, A lower bound for computing geometric spanners, Computational Geometry: Theory and Applications, volume 53, 2016, pages 21-26.
  
  
• Open Problem 14 (page 480) The geographic neighborhood graph (also known as the Yao-graph) can be constructed in O(n log n) time for points in the plane. Unlike the Theta-graph, for dimensions larger than two, it is not known if the geographic neighborhood graph can be constructed in O(n polylog(n)) time.
  
  The geographic neighborhood graph has O(n) edges and contains the minimum spanning tree. Thus, given the geographic neighborhood graph, the minimum spanning tree can be computed in O(n log n) time. It is believed that, in dimension 3, the minimum spanning tree cannot be computed significantly faster than O(n^{4/3}), see
  
  
  • Jeff Erickson, On the relative complexities of some geometric problems, Proceedings of the 7th Canadian Conference on Computational Geometry, 1995, pages 85-90.
  
  
  
• Open Problem 16 (page 480) What is the largest possible value of the ratio wt(T_0)/wt(TSP(S)), over all sets S of n points in R^d and all 2-optimal tours T_0 of S?
  
  
  • U. A. Brodowsky and S. Hougardy (The approximation ratio of the 2-opt heuristic for the Euclidean traveling salesman problem) prove that, for d=2, the answer is Theta(log n / loglog n).
  • See also: U. A. Brodowsky, S. Hougardy, and X. Zhong (The approximation ratio of the k-opt heuristic for the Euclidean traveling salesman problem).
  
  
  
• Open Problem 18 (page 480) Does there exist a set S of n points in R^d, such that for any real constant t>1, every t-spanner for S with spanner diameter O(log n) has weight Omega(log n) times the weight of a minimum spanning tree of S?
  
  
  • Y. Dinitz, M. Elkin, and S. Solomon (Low-light trees, and tight lower bounds for Euclidean spanners, Discrete & Computational Geometry, volume 43, 2010, pages 736-783) solve this problem:
    
    Consider the set S={1,2,...,n} of points on the real line.
    
    
    • If a connected graph with vertex set S has hop-diameter O(log n), then it has weight Omega(MST log n).
    • If a connected graph with vertex set S has weight O(MST log n), then it has hop-diameter Omega(log n).
  
  
  • M. Elkin and S. Solomon (Narrow-shallow-low-light trees with and without Steiner points, SIAM Journal on Discrete Mathematics, volume 25, 2011, pages 181-210) prove that the same result holds if Steiner points are allowed.
  
  
  
• Open Problem 19 (page 480) Let S be a set of n points in R^d, let t>1 be a real constant, and let k>3 be an integer. Give a formal proof that there exists an algorithm that computes, in O(n log n + k n alpha_k(n)) time, a t-spanner for S, having O(k n alpha_k(n)) edges, and whose spanner diameter is less than or equal to k.
  
  
  • S. Solomon (Sparse Euclidean spanners with tiny diameter, ACM Transactions on Algorithms, volume 9, 2013, Article 28) solves this problem. In fact, the running time of his algorithm is O(n log n).
  
  
  
• 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.
    
    
  • See also H. Le, L. Milenkovic, and S. Solomon, Sparse Euclidean spanners with tiny diameter: a tight lower bound.
  
  
  
• Open Problem 22 (page 481) Is there an algebraic computation-tree algorithm that, when given a set S of n points in R^d and a real constant t>1, computes, in O(n log n) time, a t-spanner for S, whose weight is proportional to the weight of a minimum spanning tree of S? Can such a spanner of bounded degree be computed in O(n log n) time?
  
  
  • H. Le and S. Solomon (Towards a unified theory of light spanners I: Fast (yet optimal) constructions) solve this problem: The answers to both questions are ``yes''.
  
  
  
• Open Problems 26, 27, and 28 (page 481)
  • Is there an algorithm that constructs a k-fault-tolerant t-spanner with O(kn) edges in O(n log n + kn) time?
  • Is there an algorithm that constructs a k-fault-tolerant t-spanner of degree O(k) in O(n log n + kn) time?
  • Is there an algorithm that constructs, in O(n log n + kn) time, a k-fault-tolerant t-spanner, whose weight is bounded by O(k^2) times the weight of a minimum spanning tree of S?
  
  
  • S. Solomon (Fault-tolerant spanners for doubling metrics: better and simpler) presents an O(n log n + k^2 n)-time algorithm that constructs a k-fault-tolerant t-spanner of maximum degree O(k^2), spanner diameter O(log n), and weight O(k^2 log n) times the weight of a minimum spanning tree.
    
    
  • S. Solomon (From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics) presents an O(n log n + kn)-time algorithm that constructs a k-fault-tolerant t-spanner of maximum degree O(k), spanner diameter O(log n), and weight O(k^2 + k log n) times the weight of a minimum spanning tree.
    
    
  • H. Le, S. Solomon, and C. Than (Optimal fault-tolerant spanners in Euclidean and doubling metrics: Breaking the Omega(log n) lightness barrier) present an O(n log n + kn)-time algorithm that constructs a k-fault-tolerant t-spanner of maximum degree O(k) and weight O(k^2) times the weight of a minimum spanning tree.