Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons

DOI10.1007/978-3-662-48350-3_3zbMath1465.68263OpenAlexW1930762694MaRDI QIDQ3452765

Helmut Alt, Christian Knauer, Mark T. 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) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Approximation algorithms (68W25)

Related Items (3)

Approximating Smallest Containers for Packing Three-Dimensional Convex Objects ⋮ Packing convex polygons in minimum-perimeter convex hulls ⋮ Parameterized complexity of strip packing and minimum volume packing

Cites Work

• Unnamed Item
• Unnamed Item
• A \((5/3+\varepsilon)\)-approximation for strip packing
• Finding the upper envelope of n line segments in O(n log n) time
• Cutting and packing optimization. Problems modeling and solution methods.
• Optimal packing and covering in the plane are NP-complete
• Multiple translational containment. II: Exact algorithms
• Aligning two convex figures to minimize area or perimeter
• Bundling Three Convex Polygons to Minimize Area or Perimeter
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• MINIMUM AREA CONVEX PACKING OF TWO CONVEX POLYGONS

This page was built for publication: Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons