Partitioning orthogonal polygons into \(\leq 8\)-vertex pieces, with application to an art gallery theorem (Q340521): Difference between revisions

A simple polyomino is the closed region of the plane bounded by a closed (not self-intersecting) polygon, whose angles are all \(\pi /2\) (convex) or \(3\pi /2\) (reflex). The authors prove that any simple polyomino of \(n\) vertices can be partitioned into at most \([\frac {3n+4}{16}]\) simple polyominoes of at most \(8\) vertices. A corollary of this result directly implies an earlier result of \textit{A. Aggarwal} [The art gallery theorem: its variations, applications, and algorithmic aspects. Johns Hopkins University (PhD Thesis) (1984)] and answers two questions raised in Section 3.4 of \textit{J. O'Rourke} [Art gallery theorems and algorithms. New York-Oxford: Oxford University Press (1987)].