**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).

- 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:
**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.

- Augustine, Eppstein, and Wortman
(Approximate
weighted farthest neighbors and minimum dilation stars)
prove the following:
**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.

- 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:
**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.

- 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:
**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.

- Liam Roditty (Fully dynamic geometric spanners, Proceedings of
the 23rd ACM Symposium on Computational Geometry, 2007,
pages 373-380) proves the following:
**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.