Geometric Spanner of Segments (Algorithms and Computation)

Abstract

Geometric spanner is a fundamental structure in computational geometry and plays an important role in many geometric networks design applications. In this paper, we consider a generalization of the classical geometric spanner problem (called segment spanner): Given a set S of disjoint 2-D segments, find a spanning network G with minimum size so that for any pair of points in S, there exists a path in G with length no more than t times their Euclidean distance. Based on a number of interesting techniques (such as weakly dominating set, strongly dominating set, and interval cover), we present an efficient algorithm to construct the segment spanner. Our approach first identifies a set of Steiner points in S, then construct a point spanner for them. Our algorithm runs in O(|Q| + n 2 logn) time, where Q is the set of Steiner points. We show that Q is an O(1)-approximation in terms of its size when S is relatively “well” separated by a constant. For arbitrary rectilinear segments under L 1 distance, the approximation ratio improves to 2.