Published in

Elsevier, Computational Geometry, (59), p. 13-25, 2016

DOI: 10.1016/j.comgeo.2016.07.003

Links

Tools

Export citation

Search in Google Scholar

Partitioning orthogonal polygons into ≤ 8-vertex pieces, with application to an art gallery theorem

Journal article published in 2016 by Ervin Győri, Tamás Róbert Mezei ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

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. © 2016 Elsevier B.V.