Lower bounds for computing geometric spanners and approximate shortest paths

AbstractWe consider the problems of constructing geometric spanners, possibly containing Steiner points, for a set of n input points in d-dimensional space Rd, and constructing spanners and approximate shortest paths among a collection of polygonal obstacles on the plane. The complexities of these problems are shown to be Ω(nlogn) in the algebraic computation tree model. Since O(nlogn)-time algorithms are known for solving these problems, our lower bounds are tight up to a constant factor