کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420788 683982 2006 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Orthogonal art galleries with interior walls
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Orthogonal art galleries with interior walls
چکیده انگلیسی

Consider an art gallery formed by a polygon on n vertices with m pairs of vertices joined by interior diagonals, the interior walls. Suppose that all walls (interior as well as exterior) are horizontal or vertical and each interior wall has an arbitrarily placed, arbitrarily small doorway. We show that the minimum number of guards that suffice to guard all such art galleries with n vertices and m   interior walls is min{⌊(n+2m)/4⌋,⌊(n+3⌊n/2⌋+m-2)/8⌋}min{⌊(n+2m)/4⌋,⌊(n+3⌊n/2⌋+m-2)/8⌋}.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 11, 1 July 2006, Pages 1563–1569
نویسندگان
, ,