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,rk)), where r is the number of corners of P. Moreover, the algorithm leads naturally to a decomposition of P into simpler polyominoes.
On Computing the Degree of Convexity of Polyominoes / Stefano Brocchi; Giuseppa Castiglione; Paolo Massazza. - In: ELECTRONIC JOURNAL OF COMBINATORICS. - ISSN 1077-8926. - ELETTRONICO. - 22:(2015), pp. 1-13.