کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952109 | 1442015 | 2017 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The within-strip discrete unit disk cover problem
ترجمه فارسی عنوان
دیسک واحد جداگانه در داخل نوار مشکل را پوشش می دهد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
هندسه محاسباتی، پوشش مجموعه هندسی الگوریتم های تقریبی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We present a study of the Within-Strip Discrete Unit Disk Cover (WSDUDC) problem, which is a restricted version of the Discrete Unit Disk Cover (DUDC) problem. For the WSDUDC problem, there exist a set of points and a set of unit disks in the plane, and the points and disk centres are confined to a strip of fixed width. An optimal solution to the WSDUDC problem is a subset of the disks of minimum cardinality that covers all points in the input set. We describe two approximation algorithms for the problem: a 3-approximate algorithm which applies for strips of width at most 0.8 units, and a general scheme for any strip with less than unit width. We prove that the WSDUDC problem is NP-hard on strips of any fixed width, which is our most interesting result from a theoretical standpoint. The result is also quite surprising, since a number of similar problems are tractable on strips of fixed width. Finally, we discuss how these results may be applied to known DUDC approximation algorithms.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 674, 25 April 2017, Pages 99-115
Journal: Theoretical Computer Science - Volume 674, 25 April 2017, Pages 99-115
نویسندگان
Robert Fraser, Alejandro López-Ortiz,