کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437500 690150 2011 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Guarding a set of line segments in the plane
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Guarding a set of line segments in the plane
چکیده انگلیسی

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