Article ID Journal Published Year Pages File Type
4950906 Information Processing Letters 2017 7 Pages PDF
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
, ,