Geometric Spanner of Objects under L 1 Distance.

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 the following generalized geometric spanner problem under L₁ distance: Given a set of disjoint objects S, find a spanning network G with minimum size so that for any pair of points in different objects of S, there exists a path in G with length no more than t times their L₁ distance, where t is the stretch factor. Specifically, we focus on three types of objects: rectilinear segments, axis aligned rectangles, and rectilinear monotone polygons. By combining ideas of t-weekly dominating set, walls, aligned pairs and interval cover, we develop a 4-approximation algorithm (measured by the number of Steiner points) for each type of objects. Our algorithms run in near quadratic time, and can be easily implemented for practical applications. [ABSTRACT FROM AUTHOR]