How many diagonal rectangles are needed to cover an orthogonal polygon? (Q1577551)

A polygon whose edges are horizontal and vertical is called ``orthogonal''. A rectangle with a pair of opposite corners at the vertices of an orthogonal polygon is ``diagonal'' (in that polygon). The author finds that any orthogonal polygon with \(n\) vertices can be covered by (the union of) \(\lfloor {3\over 4}n \rfloor-2-\omega\) diagonal rectangles where \(\omega=1\) when \(n=8, 12, 16\) and \(\omega =0\) otherwise. Furthermore this result is sharp and settles a problem proposed by Mamoru Watanabe at the British Combinatorial Conference 1997.