An approximation algorithm for dissecting a rectangle into rectangles with specified areas

DOI10.1016/j.dam.2006.08.005zbMath1107.68122OpenAlexW2014953934MaRDI QIDQ869574

Yuusuke Abe, Hiroshi Nagamochi

Publication date: 8 March 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.08.005

zbMATH Keywords

approximation algorithmNP-hardaspect ratiorectanglefacility layoutdivide-and-conquerdissectionfloor plan

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (4)

\(\gamma\)-soft packings of rectangles ⋮ An iterative merging algorithm for soft rectangle packing and its extension for application of fixed-outline floorplanning of soft modules ⋮ Exact and approximation algorithms for a soft rectangle packing problem ⋮ On three soft rectangle packing problems with guillotine constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The decomposition of a square into rectangles of minimal perimeter
• Improved bounds for rectangular and guillotine partitions
• On optimal guillotine partitions approximating optimal \(d\)-box partitions
• Partitioning a square into rectangles: NP-Completeness and approximation algorithms
• Tiling a rectangle with the fewest squares
• A New Mathematical-Programming Framework for Facility-Layout Design
• Optimal orientations of cells in slicing floorplan designs
• The Decomposition of a Rectangle into Rectangles of Minimal Perimeter

This page was built for publication: An approximation algorithm for dissecting a rectangle into rectangles with specified areas