Approximating minimum-area rectangular and convex containers for packing convex polygons

DOI10.1007/978-3-662-48350-3_3MaRDI QIDQ3452765zbMATH OpenOpenAlexFDO

Authors Helmut Alt, Christian Knauer, Mark de Berg

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL https://research.tue.nl/nl/publications/approximating-minimumarea-rectangular-and-convex-containers-for-packing-convex-polygons(b6af1999-df70-4cc8-8841-8b01d1d6d2eb).html

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 6698326
• scientific article; zbMATH DE number 1786500
• scientific article; zbMATH DE number 6861944
• Approximating Smallest Containers for Packing Three-Dimensional Convex Objects
• Approximation algorithms for solving packing problems of convex polygons in plane

Cites work

• A (5/3+)-approximation for strip packing
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Aligning two convex figures to minimize area or perimeter
• Bundling three convex polygons to minimize area or perimeter
• Cutting and packing optimization. Problems modeling and solution methods.
• Finding the upper envelope of n line segments in O(n log n) time
• scientific article; zbMATH DE number 1256725 (Why is no real title available?)
• scientific article; zbMATH DE number 1786500 (Why is no real title available?)
• MINIMUM AREA CONVEX PACKING OF TWO CONVEX POLYGONS
• Multiple translational containment. II: Exact algorithms
• Optimal packing and covering in the plane are NP-complete

Cited in

(11)

• Approximation algorithms for solving packing problems of convex polygons in plane
• Packing 2D disks into a 3D container
• Packing convex polygons in minimum-perimeter convex hulls
• scientific article; zbMATH DE number 6698326 (Why is no real title available?)
• Approximating Smallest Containers for Packing Three-Dimensional Convex Objects
• Enclosing a Set of Objects by Two Minimum Area Rectangles
• scientific article; zbMATH DE number 1786500 (Why is no real title available?)
• scientific article; zbMATH DE number 6861944 (Why is no real title available?)
• Scandinavian thins on top of cake: new and improved algorithms for stacking and packing
• Parameterized complexity of strip packing and minimum volume packing
• Online packing to minimize area or perimeter

This page was built for publication: Approximating minimum-area rectangular and convex containers for packing convex polygons

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