On computing the degree of convexity of polyominoes (Q490307)

Summary: In this paper we present an algorithm which has as input a convex polyomino \(P\) and computes its degree of convexity, defined as the smallest integer \(k\) such that any two cells of \(P\) can be joined by a monotone path inside \(P\) with at most \(k\) changes of direction. The algorithm uses space \(O(m + n)\) to represent a polyomino \(P\) with \(n\) rows and \(m\) columns, and has a running time \(O(\min(m; r k))\), where \(r\) is the number of corners of \(P\). Moreover, the algorithm leads naturally to a decomposition of \(P\) into simpler polyominoes.