In this paper we present a simple algorithm for computing the degree of convexity of a convex polyomino, 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. We show how it can be used to obtain an efficient algorithm for computing all k-convex polyominoes of size n. More precisely, such an algorithm uses space O(n) and runs in constant amortized time.
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
In this paper we present a simple algorithm for computing the degree of convexity of a convex polyomino, 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. We show how it can be used to obtain an efficient algorithm for computing all k-convex polyominoes of size n. More precisely, such an algorithm uses space O(n) and runs in constant amortized time.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
[29]Gascom2014.pdf
Solo gestori archvio
Tipologia:
Versione Editoriale
Dimensione
96.3 kB
Formato
Adobe PDF
|
96.3 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.
