Corner occupying theorem for the two-dimensional integral rectangle packing problem  

作　　者：HUANG WenQi YE Tao CHEN DuanBing 

机构地区：[1]Sehool of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China [2]Web Sciences Center,School of Computer Science,University of Electronic Science and Technology of China Chengdu 611731,China

出　　处：《Science China(Information Sciences)》2012年第11期2466-2472,共7页中国科学（信息科学）（英文版）

基　　金：supported by the National Natural Science Foundation of China (Grant Nos.61070235,61100144,61173180)

摘　　要：This paper proves a corner occupying theorem for the two-dimensional integral rectangle packing problem, stating that if it is possible to orthogonally place n arbitrarily given integral rectangles into an integral rectangular container without overlapping, then we can achieve a feasible packing by successively placing a rectangle onto a bottom-left corner in the container. Based on this theorem, we might develop efficient heuristic algorithms for solving the integral rectangle packing problem. In fact, as a vague conjecture, this theorem has been implicitly mentioned with different appearances by many people for a long time.This paper proves a corner occupying theorem for the two-dimensional integral rectangle packing problem, stating that if it is possible to orthogonally place n arbitrarily given integral rectangles into an integral rectangular container without overlapping, then we can achieve a feasible packing by successively placing a rectangle onto a bottom-left corner in the container. Based on this theorem, we might develop efficient heuristic algorithms for solving the integral rectangle packing problem. In fact, as a vague conjecture, this theorem has been implicitly mentioned with different appearances by many people for a long time.

关 键 词：rectangle packing bottom-left corner occupying theorem NP hard 

分 类 号：O174[理学—数学] TQ053.2[理学—基础数学]