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 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.
Brocchi, S., Castiglione, G., Massazza, P. (2015). On computing the degree of convexity of polyominoes. ELECTRONIC JOURNAL OF COMBINATORICS, 22(1), 1-13 [10.37236/3678].
On computing the degree of convexity of polyominoes
CASTIGLIONE, Giuseppa;
2015-01-01
Abstract
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 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.File | Dimensione | Formato | |
---|---|---|---|
[29]EJC2015.pdf
accesso aperto
Descrizione: Articolo principale
Tipologia:
Versione Editoriale
Dimensione
228.28 kB
Formato
Adobe PDF
|
228.28 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.