咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Approximating Smallest Contain... 收藏

Approximating Smallest Containers for Packing Three-Dimensional Convex Objects

作     者:Helmut Alt Nadja Scharf 

作者机构:Institut für Informatik Freie Universität Berlin Takustraße 9 14195 Berlin Germany 

出 版 物:《International Journal of Computational Geometry & Applications》 

年 卷 期:2018年第28卷第2期

页      面:111-128页

学科分类:07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主  题:Computational geometry packing approximation algorithm 

摘      要:We investigate the problem of computing a minimal-volume container for the non-overlapping packing of a given set of three-dimensional convex objects. Already the simplest versions of the problem are 𝒩 𝒫 -hard so that we cannot expect to find polynomial time algorithms to determine the exact solution. We give constant ratio approximation algorithms for packing axis-parallel (rectangular) cuboids under translation into an axis-parallel (rectangular) cuboid as container, for packing cuboids under rigid motions into an axis-parallel cuboid or into an arbitrary convex container, and for packing convex polyhedra under rigid motions into an axis-parallel cuboid or arbitrary convex container. This work gives the first approximability results for the computation of minimum volume containers for the objects described.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分