Name
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.
|
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-77120-3_9 | International Symposium on Algorithms and Computation |
Keywords | Field | DocType |
segment spanner,euclidean distance,2-d segment,weakly dominating set,classical geometric spanner problem,point spanner,steiner point,dominating set,geometric networks design application,geometric spanner,network design | Discrete mathematics,Dominating set,Combinatorics,Disjoint sets,Geometric spanner,Steiner point,Computational geometry,Geometric networks,Spanner,Theta graph,Mathematics | Conference |
Volume | ISSN | ISBN |
4835 | 0302-9743 | 3-540-77118-2 |
Citations | PageRank | References |
1 | 0.36 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yang Yang | 1 | 259 | 18.33 |
| Yongding Zhu | 2 | 11 | 3.06 |
| Jinhui Xu | 3 | 665 | 78.86 |
| naoki katoh | 4 | 1101 | 187.43 |