| Geometric Spanner of Objects under L1 Distance (Computing and Combinatorics) (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Computing and combinatorics : 14th annual international conference, COCOON 2008, Dalian, China, June 27-29, 2008 : proceedings : (Lecture notes in computer science ; 5092). The 14th Annual International Computing and Combinatorics Conference (COCOON 2008). 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 1 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 1 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. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||