Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons
Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons
复制标题
用于包装凸多边形的近似最小面积矩形和凸容器
DOI：
--
复制
发表时间：
2020
影响因子：
0.3
通讯作者：
Christian Knauer
中科院分区：
文献类型：
--
作者：
H. Alt;M. D. Berg;Christian Knauer
研究了用平移法求解凸多边形集不相交装箱的最小面积容器问题。特别地，我们考虑轴平行矩形或任意凸集作为容器。对于这两个np困难的优化问题，我们开发了有效的常因子近似算法。
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.