کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414621 | 680989 | 2015 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Linear time algorithm for optimal feed-link placement
ترجمه فارسی عنوان
الگوریتم زمان خطی برای بهینه سازی قرار دادن لینک خوراک
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
خوراک لینک، انحطاط، انحراف، چند ضلعی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given a polygon representing a transportation network together with a point p in its interior, we aim to extend the network by inserting a line segment, called feed-link, which connects p to the boundary of the polygon. Once a feed link is fixed, the geometric dilation of some point q on the boundary is the ratio between the length of the shortest path from p to q through the extended network, and their Euclidean distance. The utility of a feed-link is inversely proportional to the maximal dilation over all boundary points.We give a linear time algorithm for computing the feed-link with the minimum overall dilation, thus improving upon the previously known algorithm of complexity that is roughly O(nlogn)O(nlogn).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 48, Issue 3, March 2015, Pages 189–204
Journal: Computational Geometry - Volume 48, Issue 3, March 2015, Pages 189–204
نویسندگان
Marko Savić, Miloš Stojaković,