Minimum decomposition into convex binary matrices

AbstractMotivated by Intensity Modulated Radiation Therapy, we consider the problem of the minimum decomposition of an integer matrix into hv-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 hv-convex matrices or into two hv-convex polyominoes is polynomially solvable. For the decomposition into three hv-convex matrices the problem becomes NP-complete