Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950906 | Information Processing Letters | 2017 | 7 Pages |
Abstract
Let S be a set of n points in Rd and let tâ¥1 be a real number. A geometric graph G with vertex set S is called a t-spanner for S if for each two points p and q in S, there exists a path Q in G between p and q whose length is at most t times |pq|, the Euclidean distance between p and q. The geometric graph G with vertex set S is called a θ-angle-constrained t-spanner if G is a t-spanner of S and any two edges {p,q} and {p,r} in G make an angle of at least θ. In this paper, we show that there is a point set P in the plane such that for every θ>Ï/3, there is no θ-angle-constrained t-spanner on P. Moreover, we show that for θ=Ï/3 and every t<2/3, there is no θ-angle-constrained t-spanner on P. This solves an open problem posed by Paz Carmi and Michiel Smid [2].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Davood Bakhshesh, Mohammad Farshi,