This paper demonstrates a polynomial time method to compute the number of k-convex polyominoes, indicating significant improvements in computational efficiency.
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.
No takes yet. Share an insight, caveat, or question.
Guttmann et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: