کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428991 | 686987 | 2012 | 5 صفحه PDF | دانلود رایگان |
We present an art gallery theorem for simple polygons having n vertices in terms of the number, r, of reflex vertices and the number, c , of convex vertices (n=r+cn=r+c). Tight combinatorial bounds have previously been shown when 0⩽r⩽⌊c2⌋ and when r⩾5c−12r⩾5c−12. We give a lower bound construction that matches the ⌊n3⌋ sufficiency condition from the traditional art gallery theorem when ⌊c2⌋
► Art gallery theorem for simple polygons in terms of the number of reflex vertices (r), and convex vertices (c).
► Algorithm for generating lower bound constructions that match corresponding upper bounds for certain ranges of r and c is given.
► The lower bound constructions interpolate between previously known constructions for specific ranges of r and c.
Journal: Information Processing Letters - Volume 112, Issue 20, 31 October 2012, Pages 778–782