In Section 2, we de ne and recall some basic notions that are used throughout the rest of the paper. In particular, we de ne well separated pairs and strong approximate neighbors. It gives a 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 6 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 result is that of Theorem 2.