کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949162 | 1439987 | 2016 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Partitioning orthogonal polygons into ⤠8-vertex pieces, with application to an art gallery theorem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We prove that every simply connected orthogonal polygon of n vertices can be partitioned into â3n+416â (simply connected) orthogonal polygons of at most 8 vertices. It yields a new and shorter proof of the theorem of A. Aggarwal that â3n+416â mobile guards are sufficient to control the interior of an n-vertex orthogonal polygon. Moreover, we strengthen this result by requiring combinatorial guards (visibility is only needed at the endpoints of patrols) and prohibiting intersecting patrols. This yields positive answers to two questions of O'Rourke [7, Section 3.4]. Our result is also a further example of the “metatheorem” that (orthogonal) art gallery theorems are based on partition theorems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 59, December 2016, Pages 13-25
Journal: Computational Geometry - Volume 59, December 2016, Pages 13-25
نویسندگان
Ervin GyÅri, Tamás Róbert Mezei,