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 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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2012-05, Vol.160 (7-8), p.1164-1175
Main Authors: Jarray, Fethi, Picouleau, Christophe
Format: Article
Language:English
Subjects:
[formula omitted]-complete
Combinatorics
Computer Science
Convex polyomino
Data Structures and Algorithms
Discrete Mathematics
Intensity Modulated Radiation Therapy
Mathematics
Matrix decomposition
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Motivated 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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2012.01.013