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

DOI10.1016/J.DAM.2006.08.005MaRDI QIDQ869574zbMATH OpenOpenAlexFDO

Authors Hiroshi Nagamochi, Yuusuke Abe

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-hardrectangledivide-and-conquerfacility layoutaspect ratiodissectionfloor plan

Mathematics Subject Classification ID

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

Recommendations

• Algorithms and Computation
• The Decomposition of a Rectangle into Rectangles of Minimal Perimeter
• Partitioning a square into rectangles: NP-Completeness and approximation algorithms
• On three soft rectangle packing problems with guillotine constraints
• Partitioning a rectangle into small perimeter rectangles

Cites work

• scientific article; zbMATH DE number 1670543 (Why is no real title available?)
• scientific article; zbMATH DE number 1229395 (Why is no real title available?)
• scientific article; zbMATH DE number 1256699 (Why is no real title available?)
• scientific article; zbMATH DE number 1303579 (Why is no real title available?)
• A new mathematical-programming framework for facility-layout design
• Improved bounds for rectangular and guillotine partitions
• On optimal guillotine partitions approximating optimal \(d\)-box partitions
• Optimal orientations of cells in slicing floorplan designs
• Partitioning a square into rectangles: NP-Completeness and approximation algorithms
• The Decomposition of a Rectangle into Rectangles of Minimal Perimeter
• The decomposition of a square into rectangles of minimal perimeter
• Tiling a rectangle with the fewest squares

Cited in

(9)

• Approximation algorithms for partitioning a rectangle with interior points
• The Decomposition of a Rectangle into Rectangles of Minimal Perimeter
• An iterative merging algorithm for soft rectangle packing and its extension for application of fixed-outline floorplanning of soft modules
• On three soft rectangle packing problems with guillotine constraints
• A modified DIviding RECTangles algorithm for a problem in astrophysics
• \(\gamma\)-soft packings of rectangles
• Rectangle transformation problem
• Algorithms and Computation
• Exact and approximation algorithms for a soft rectangle packing problem

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

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