We will prove that in the algebraic computation tree model, any algorithm that constructs a $t$-spanner for any set of $n$ points in $d$-dimensional space, has an $\Omega(n \log n)$ worst-case running time. This follows by a simple reduction from the element uniqueness problem.

We also consider the spanner problem for the case when the input points are pairwise distinct. For such inputs, this reduction obviously does not work. We will prove that the $\Omega(n \log n)$ lower bound for constructing $t$-spanners still holds for inputs consisting of pairwise distinct points. This lower bound is proved by using Ben-Or's theorem. Note that this theorem cannot be applied directly, because it does not assume any restriction on the input. We will show, however, how to circumvent this.

(Joint work with Danny Chen and Gautam Das in 1996.)