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.
2015
Settore INF/01 - Informatica
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].
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/138112
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact