
Lower Bounds for Computing Geometric
Spanners and Approximate Shortest Paths
Danny Z. Chen? Gautam Dasy Michiel Smidz
April 22, 1996
Abstract
We consider the problems of constructing geometric spanners, possibly containing Steiner points, for sets of points in the ddimensional space IRd, and constructing spanners and approximate shortest paths among a collection of polygonal obstacles in the plane. The complexities of these problems are shown to be ?(n log n) in the algebraic computation tree model. Since O(n log n)time algorithms are known for solving these problems, our lower bounds are tight up to a constant factor.
1 Introduction
Geometric spanners are data structures that approximate the complete graph on a set of points in the ddimensional space IRd, in the sense that the shortest path (based on such a spanner) between any pair of given points is not more than a factor of t longer than the distance between the points in IRd.
Let o be a fixed constant such that 1 <= o <= 1. Throughout this paper, we measure distances between points in the ddimensional space IRd with the Lometric, where d >= 1 is an integer constant. Let S be a set of n points in IRd. We consider the kind of graphs G = (V; E) such that (i) V is a set of points in IRd, (ii) S ? V , and (iii) the edges of G are straightline segments in IRd that connect pairs of points in V . The length of an edge in G is defined as the Lodistance between its endpoints. In such a graph, the length of a path is defined as the sum of the lengths of the edges on the path.
Let t > 1 be any real number. Consider a graph G = (V; E) that satisfies (i), (ii), and (iii), such that for every pair p; q of points of S, there is a path in G between p
?Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN
46556, USA. Email: dchen@euclid.cse.nd.edu. The research of this author was supported in part
by the National Science Foundation under Grant CCR9623585.
yMath Sciences Dept., The University of Memphis, Memphis, TN 38152, USA. Supported in part
by NSF Grant CCR9306822. Email: dasg@next1.msci.memphis.edu.
zDepartment of Computer Science, King's College London, Strand, London WC2R 2LS, United
Kingdom. Email: michiel@dcs.kcl.ac.uk.