Approximating minimum-area rectangular and convex containers for packing convex polygons
| Autor: | Alt, H.W., de Berg, M.T., Knauer, C., Bansel, N., Finocchi, I. |
|---|---|
| Přispěvatelé: | Algorithms, Geometry and Applications |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Convex analysis
Convex hull Discrete mathematics 021103 operations research 0211 other engineering and technologies Convex set Proper convex function 0102 computer and information sciences 02 engineering and technology Subderivative 01 natural sciences Combinatorics 010201 computation theory & mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Convex polytope Convex optimization Convex combination Mathematics |
| Zdroj: | Algorithms-ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, 25-34 STARTPAGE=25;ENDPAGE=34;TITLE=Algorithms-ESA 2015 Algorithms-ESA 2015 ISBN: 9783662483497 |
| ISSN: | 0302-9743 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|