2013 | OriginalPaper | Buchkapitel
How to Decompose a Binary Matrix into Three hv-convex Polyominoes
verfasst von : Andrea Frosini, Christophe Picouleau
Erschienen in: Discrete Geometry for Computer Imagery
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given a binary matrix, deciding wether it can be decomposed into three
hv
-convex matrices is an
$\cal NP$
-complete problem, whereas its decomposition into two
hv
-convex matrices or two
hv
-polyominoes can be performed in polynomial time. In this paper we give a polynomial time algorithm that decomposes a binary matrix into three
hv
-polyominoes, if such a decomposition exists. These problems are motivated by the Intensity Modulated Radiation Therapy (IMRT).