Minimum decomposition into convex binary matrices

Motivated by Intensity Modulated Radiation Therapy, we consider the problem of the minimum decomposition of an integer matrix into hvhv-convex matrices with time and cardinality objectives. We study the special case where the matrix to decompose is a binary matrix (in this case, time decomposition and cardinality decomposition are the same). We prove that the decomposition into two hvhv-convex matrices or into two hvhv-convex polyominoes is polynomially solvable. For the decomposition into three hvhv-convex matrices the problem becomes NPNP-complete.