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 show that, for any fixed integer k > 2, the number of polyominoes of area n and degree of convexity at most k can be computed in polynomial time using O(n(4)) space.
Efficient counting of k -convex polyominoes
Massazza P.
2025-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 show that, for any fixed integer k > 2, the number of polyominoes of area n and degree of convexity at most k can be computed in polynomial time using O(n(4)) space.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
