On Counting L-Convex Polyominoes

A convex polyomino P is L-convex if any two cells of P can be joined by a monotone path inside P with at most one change of direction. In this paper we show that the problem of computing the number of L-convex polyominoes of area n can be solved in polynomial time using O(n^4) space. We designed a C++ program to significantly extend the counting sequence of L-convex polyominoes and to improve the estimate of the associated growth constant.