Covering rectangles by few monotonous polyominoes

Abstract

A monotonous polyomino is formed by all lattice unit squares met by the graph of some fixed monotonous continuous function $f:[a,b]\to \mathbb{R}$ with $f(k)\notin \mathbb{Z}$ whenever $k\in \mathbb{Z}$. Our main result says that the least cardinality of a covering of a lattice $(m\times n)$-rectangle by monotonous polyominoes is $\lceil \frac{2}{3}\left(m+n-\sqrt{m^2+n^2-mn}\right)\rceil$. The paper is motivated by a problem on arrangements of straight lines on chessboards.