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

M.T. de Berg, H. Alt, C. Knauer

Research output: Contribution to journalArticleAcademicpeer-review

286 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)1–10
Number of pages10
JournalJournal of Computational Geometry
Volume8
Issue number1
DOIs
Publication statusPublished - 2017

Keywords

  • Discrete Algorithms

Fingerprint

Dive into the research topics of 'Approximating minimum-area rectangular and convex containers for packing convex polygons'. Together they form a unique fingerprint.

Cite this