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

Helmut Alt, Mark de Berg, Christian Knauer


We investigate the problem of finding a minimum-area container for the disjoint packing of a set of convex polygons by translations. In particular, we consider axis-parallel rectangles or arbitrary convex sets as containers. For both optimization problems which are NP-hard we develop efficient constant factor approximation algorithms.

Full Text:



ISSN: 1920-180X