What type of study is this?

This is a Quantitative Study study.

October 17, 2025RAIRO - Theoretical Informatics and Applications0 citationsOpen Access

Efficient counting of k-convex polyominoes

AGA J GuttmannThe University of Melbourne PMPaolo MassazzaUniversity of Insubria

Key Points

The number of k-convex polyominoes can be efficiently counted based on the area.
The proposed method operates in polynomial time with a space complexity of O(n^4).
The approach focuses on the degree of convexity, highlighting changes of direction in the structure.
This work extends counting techniques for convex polyominoes, providing new insights into combinatorial geometry.

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.

Perguntar à IA

Bookmark

View Full Paper