کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6868402 | 1439973 | 2018 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Constrained generalized Delaunay graphs are plane spanners
ترجمه فارسی عنوان
نمودارهای دلونای محدود شده محدود هستند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار دلونی، نسبت پوشش محدودیت ها،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We look at generalized Delaunay graphs in the constrained setting by introducing line segments which the edges of the graph are not allowed to cross. Given an arbitrary convex shape C, a constrained Delaunay graph is constructed by adding an edge between two vertices p and q if and only if there exists a homothet of C with p and q on its boundary that does not contain any other vertices visible to p and q. We show that, regardless of the convex shape C used to construct the constrained Delaunay graph, there exists a constant t (that depends on C) such that it is a plane t-spanner of the visibility graph. Furthermore, we reduce the upper bound on the spanning ratio for the special case where the empty convex shape is an arbitrary rectangle to 2â
(2l/s+1), where l and s are the length of the long and short side of the rectangle.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 74, October 2018, Pages 50-65
Journal: Computational Geometry - Volume 74, October 2018, Pages 50-65
نویسندگان
Prosenjit Bose, Jean-Lou De Carufel, André van Renssen,