A dual of the rectangle-segmentation problem for binary matrices

MaRDI QIDQ2380244zbMATH OpenFDO

Authors Thomas Kalinowski

Publication date 26 March 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/228955, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r89.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Optimality conditions and duality in mathematical programming (90C46)

Review text

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

Recommendations

• Optimal matrix-segmentation by rectangles
• Minimum decomposition into convex binary matrices
• An algorithm for covering polygons with rectangles
• How to decompose a binary matrix into three hv-convex polyominoes
• The Decomposition of a Rectangle into Rectangles of Minimal Perimeter

Cited in

(7)

• Binary segmentation for matrix and vector operations
• Combinatorial Benders cuts for decomposing IMRT fluence maps using rectangular apertures
• Décomposition Rectangulaire Optimale D’une Relation Binaire: Application Aux Bases De Données Documentaires
• Close-to-optimal algorithm for rectangular decomposition of 3D shapes.
• Optimal matrix-segmentation by rectangles
• A hybrid heuristic for the rectilinear picture compression problem
• Orthogonal dissection into few rectangles

This page was built for publication: A dual of the rectangle-segmentation problem for binary matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380244)