Lower bounds for computing geometric spanners and approximate shortest paths . The optimality of the running time follows from Chen et al. It gives a Euclidean k fault tolerant t spanner, in which the degree of each vertex is bounded by a constant, and whose weight is proportional to the weight of a minimum spanning tree. Chen et al. Therefore, the result of Theorem 2 is optimal for constant values of k.
Some interesting problems remain to be solved.
D. Z. Chen, G. Das, and M. Smid. Lower bounds for computing geometric spanners and approximate shortest paths . If k is a constant, then this result is optimal. The optimality of the running time follows from Chen et al. If k is a constant, then the best results are those of Theorems 2 and 3.