Partitioning orthogonal polygons into ≤ 8-vertex pieces, with application to an art gallery theorem
详细信息 查看全文
- 作者：Ervin Győria ; b ; 1 ; ervin@renyi.hu" class="auth_mail" title="E-mail the corresponding author ; Tamá ; s Ró ; bert Mezeib ; tamasrobert.mezei@gmail.com" class="auth_mail" title="E-mail the corresponding author
- 关键词：Art gallery ; Polyomino partition ; Mobile guard
- 刊名：Computational Geometry
- 出版年：2016
- 出版时间：December 2016
- 年：2016
- 卷：59
- 期：Complete
- 页码：13-25
- 全文大小：487 K
文摘
We prove that every simply connected orthogonal polygon of n vertices can be partitioned into 4c05fecd0ef3f41e1f6b7492245">
(simply connected) orthogonal polygons of at most 8 vertices. It yields a new and shorter proof of the theorem of A. Aggarwal that 4c05fecd0ef3f41e1f6b7492245"> 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.
(simply connected) orthogonal polygons of at most 8 vertices. It yields a new and shorter proof of the theorem of A. Aggarwal that 4c05fecd0ef3f41e1f6b7492245"> 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.