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

Helmut Alt, Mark de Berg, Christian Knauer

Abstract


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:

PDF


DOI: http://dx.doi.org/10.20382/jocg.v8i1a1

ISSN: 1920-180X