Geometric Spanner of Objects under L1 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 L1 distance: Given a set of disjoint objects 5, 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 L1 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.
Yongding Zhu Jinhui Xu Yang Yang Naoki Katoh Shin-ichi Tanigawa
Department of Computer Science and Engineering State University of New York at Buffalo Buffalo, NY 1 Department of Architecture and Architectural Systems Kyoto University,Japan Department of Architecture and Architectural Systems Kyoto University, Japan
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
395-404
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）