کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950906 | 1441042 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Angle-constrained spanners with angle at least Ï/3
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
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].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 120, April 2017, Pages 44-46
Journal: Information Processing Letters - Volume 120, April 2017, Pages 44-46
نویسندگان
Davood Bakhshesh, Mohammad Farshi,