Geometric Spanner of Segments
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 spann
- PDF / 587,730 Bytes
- 13 Pages / 430 x 660 pts Page_size
- 46 Downloads / 181 Views
2
Department of Computer Science and Engineering State University of New York at Buffalo Buffalo, NY 14260, USA {yyang6,yzhu3,jinhui}@cse.buffalo.edu Department of Architecture and Architectural Systems Kyoto University, Japan [email protected]
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| + n2 log n) 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 L1 distance, the approximation ratio improves to 2.
1
Introduction
In this paper, we consider the following generalization of the classical geometric spanner problem: Given a set O of n disjoint objects in Euclidean space and a constant t > 1, construct a graph G for O of minimum size so that for any pair of points pi ∈ oi and pj ∈ oj , there exists a path P (pi , pj ) in G whose total length is at most t × d(pi , pj ), where oi and oj are objects in O and d(pi , pj ) is the Euclidean distance between pi and pj . The path P (pi , pj ) consists of three parts, P1 , P2 and P3 , where P1 and P3 are the portions of P (pi , pj ) inside oi and oj respectively. We assume that there implicitly exists an edge (or path) between any pair of points inside each object o ∈ O. Thus, the objective of minimizing
The research of this work was supported in part by National Science Foundation (NSF) through a CAREER award CCF-0546509 and a grant IIS-0713489. Corresponding author. The research of this author was supported by the project New Horizons in Computing, Grant-in-Aid for Scientific Research on Priority Areas,MEXT Japan.
T. Tokuyama (Ed.): ISAAC 2007, LNCS 4835, pp. 75–87, 2007. c Springer-Verlag Berlin Heidelberg 2007
76
Y. Yang et al.
the size of G is equivalent to minimizing the total number of vertices, and edges between vertices in different objects. In this paper, we consider the case where all objects are disjoint 2-D line segments. Spanner is a fundamental structure in computational geometry and finds applications in many different areas. Extensive researches have been done on this structure and a number of interesting results have been obtained [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]. Almost all previous results consider the case in which the objects are points and seek to minim
Data Loading...
