کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437500 | 690150 | 2011 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Guarding a set of line segments in the plane
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider the following problem: Given a finite set of straight line segments in the plane, find a set of points of minimum size, so that every segment contains at least one point in the set. This problem can be interpreted as looking for a minimum number of locations of policemen, guards, cameras or other sensors, that can observe a network of streets, corridors, tunnels, tubes, etc. We show that the problem is strongly NP-complete even for a set of segments with a cubic graph structure, but in P for tree structures.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 412, Issue 15, 25 March 2011, Pages 1313-1324
Journal: Theoretical Computer Science - Volume 412, Issue 15, 25 March 2011, Pages 1313-1324