A note on the contractions for orthogonal polygons (Q686493)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on the contractions for orthogonal polygons |
scientific article |
Statements
A note on the contractions for orthogonal polygons (English)
0 references
4 January 1994
0 references
An orthogonal polygon \(P\) in the plane is a polygon whose edges are either vertical or horizontal. A vertex is called an inner resp. outer vertex if his interior angle in the polygon equals \(3\pi/2\) resp. \(\pi/2\). Let \(n(P)\) and \(i(P)\) be the number of vertices resp. inner vertices. The author defines a contraction for orthogonal polygons and proves that \(n(P)= 2i(P)+4\) as well that each orthogonal polygon can be transformed into a rectangle by a sequence of contractions. As a corollary he obtains the result of \textit{J. Kahn}, \textit{M. Klawe} and \textit{D. Kleitman} [Traditional galleries require fewer watchmen, SIAM J. Algebraic Discrete Methods 4, 194-206 (1983; Zbl 0533.05021)] that the minimum number of watchmen which are necessary to watch an orthogonal polygon is not larger than \(\lfloor n/4\rfloor\). Moreover, a property of the maximal rectangles contained in orthogonal polygons is presented.
0 references
art gallery theorem
0 references
polyomino
0 references
orthogonal polygon
0 references
contraction
0 references
rectangle
0 references