The degree of convexity of a convex polyomino P is 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. In this paper we present a simple algorithm for computing the degree of convexity of a convex polyomino and we show how it can be used to design an algorithm that generates, given an integer k, all k-convex polyominoes of area n in constant amortized time, using space O(n). Furthermore, by applying few changes, we are able to generate all convex polyominoes whose degree of convexity is exactly k.

Brocchi, S., Castiglione, G., Massazza, P. (2017). On the exhaustive generation of k-convex polyominoes. THEORETICAL COMPUTER SCIENCE, 664, 54-66 [10.1016/j.tcs.2016.02.006].

On the exhaustive generation of k-convex polyominoes

Castiglione, Giuseppa;
2017-01-01

Abstract

The degree of convexity of a convex polyomino P is 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. In this paper we present a simple algorithm for computing the degree of convexity of a convex polyomino and we show how it can be used to design an algorithm that generates, given an integer k, all k-convex polyominoes of area n in constant amortized time, using space O(n). Furthermore, by applying few changes, we are able to generate all convex polyominoes whose degree of convexity is exactly k.
2017
Settore INF/01 - Informatica
Brocchi, S., Castiglione, G., Massazza, P. (2017). On the exhaustive generation of k-convex polyominoes. THEORETICAL COMPUTER SCIENCE, 664, 54-66 [10.1016/j.tcs.2016.02.006].
File in questo prodotto:
File Dimensione Formato  
[32] TCS_Bertoni_2017.pdf

Solo gestori archvio

Tipologia: Versione Editoriale
Dimensione 503.73 kB
Formato Adobe PDF
503.73 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/254431
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 5
social impact