page 1  (15 pages) 2

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 d-dimensional 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 d-dimensional 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 d-dimensional space IRd with the Lo-metric, 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 straight-line segments in IRd that connect pairs of points in V . The length of an edge in G is defined as the Lo-distance 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. E-mail: dchen@euclid.cse.nd.edu. The research of this author was supported in part by the National Science Foundation under Grant CCR-9623585.
yMath Sciences Dept., The University of Memphis, Memphis, TN 38152, USA. Supported in part by NSF Grant CCR-9306822. E-mail: dasg@next1.msci.memphis.edu.
zDepartment of Computer Science, King's College London, Strand, London WC2R 2LS, United Kingdom. E-mail: michiel@dcs.kcl.ac.uk.