In this paper we present an algorithm which has as input a convex polyomino P and computes its degree of convexity, deﬁned 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 time complexity 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.
|Data di pubblicazione:||2015|
|Titolo:||On computing the degree of convexity of polyominoes|
|Rivista:||ELECTRONIC JOURNAL OF COMBINATORICS|
|Codice identificativo ISI:||WOS:000348239800001|
|Codice identificativo Scopus:||2-s2.0-84920928449|
|Appare nelle tipologie:||Articolo su Rivista|