A Dual of the Rectangle-Segmentation Problem for Binary Matrices

  • Thomas Kalinowski

Abstract

We consider the problem to decompose a binary matrix into a small number of binary matrices whose 1-entries form a rectangle. We show that the linear relaxation of this problem has an optimal integral solution corresponding to a well known geometric result on the decomposition of rectilinear polygons.

Published
2009-07-24
Article Number
R89