직사각형 패킹

Rectangle packing

직사각형 패킹은 두 개의 작은 직사각형이 겹치지 않도록 작은 직사각형 세트를 주어진 큰 다각형 안에 배치할 수 있는지 여부를 결정하는 데 목적이 있는 패킹 문제입니다.이 문제의 몇 가지 변형이 연구되어 왔다.

직사각형에 동일한 직사각형 채우기

이 변형에서는 크기(l,w)의 단일 직사각형과 크기(L,W)의 더 큰 직사각형 인스턴스가 여러 개 있습니다.목표는 작은 직사각형을 큰 직사각형에 가능한 한 많이 채우는 것입니다(작은 직사각형과 큰 직사각형 사이에 겹치지 않습니다).문제의 일반적인 제약사항으로는 작은 직사각형 회전을 90° 배수로 제한하고 작은 직사각형 각각이 큰 직사각형과 직교하도록 요구하는 것이 있다.

이 문제는 팔레트, 특히 우드펄프 보관함에 박스를 적재하는 것과 같은 몇 가지 용도로 사용됩니다.그 결과, 사이즈(1600,1230)[1]의 큰 직사각형에 사이즈(137,95)의 작은 직사각형 147개를 채울 수 있다.

직선 다각형에서 동일한 정사각형 채우기

평면에서 직선 다각형(변과 직각으로 만나는) R, R의 점 집합 S 및 동일한 정사각형 집합이 주어지면, 목표는 S의 점으로 채워질 수 있는 겹치지 않는 가장 많은 수의 정사각형을 찾는 것이다.

S의 각 점 p에 대해 p를 중심으로 한 정사각형을 배치했다고 가정합니다.G를 이 정사각형의 교차 그래프라고 합니다S.정사각형 패킹은 G의 독립S 집합과 동일합니다. 가장 큰 정사각형 패킹을 찾는 것은 NP-hard입니다. 이를 [2]3SAT에서 줄임으로써 증명할 수 있습니다.

지정된 직사각형에 서로 다른 직사각형 채우기

이 변형에서는 작은 직사각형은 길이와 폭이 다를 수 있으며, 주어진 큰 직사각형에 채워야 합니다.이러한 패킹이 존재하는지 여부를 결정하는 문제는 NP-hard입니다.이는 3-파티션의 감소로 입증될 수 있습니다.3m 양의 정수를1 가진 3분할의 예: a, ..., a3m, 총합이 m T인 경우, 우리는 직사각형 i의 길이가 + m이 되도록i 폭 1인 3m의 작은 직사각형을 구축한다.큰 직사각형의 너비는 m, 길이는 T + 3m입니다.3분할 인스턴스(instance)에 대한 모든 솔루션은 각 서브셋의 총 길이가 정확히 T가 되도록 직사각형의 패킹을 m개의 서브셋으로 유도하여 큰 직사각형에 정확히 맞도록 합니다.반대로 큰 직사각형의 패킹에는 "구멍"이 없어야 하므로 직사각형이 회전하지 않아야 합니다.따라서 각 행에 정확히 T의 총 길이가 있는 직사각형이 들어 있는 경우 패킹에는 정확히 m개의 행이 포함되어야 합니다.이는 3 파티션 인스턴스의 [3][4]솔루션에 해당합니다.

패킹이 정확해야 한다는 추가적인 제한이 있을 경우(낭비되는 공간이 없음), 작은 직사각형을 90°의 배수만큼만 회전시킬 수 있습니다.이 경우 문제는 NP에 있습니다.이 요건이 없으면 작은 직사각형을 임의의 각도로 회전시킬 수 있다.이 일반적인 경우에는 해결책을 [4]검증하기가 훨씬 어렵기 때문에 문제가 NP에 있는지 여부가 명확하지 않습니다.

최소 면적 직사각형에서 서로 다른 직사각형 채우기

이 변형에서는 작은 직사각형의 길이와 폭이 다를 수 있으며, 그 방향은 고정되어 있습니다(회전할 수 없습니다).목표는 최소 면적의 둘러싸인 직사각형에 그것들을 채우는 것이며, 둘러싸인 직사각형의 너비나 높이에 경계가 없습니다.이 문제는 이미지를 하나의 큰 이미지로 결합하는 데 중요한 응용 프로그램이 있습니다.하나의 큰 이미지를 로드하는 웹 페이지는 웹 서버에서 각 이미지를 요구할 때 오버헤드가 발생하기 때문에 같은 페이지에서 여러 개의 작은 이미지를 로드하는 것보다 브라우저에서 더 빨리 렌더링됩니다.문제는 일반적으로 NP-complete이지만 작은 [5][6]인스턴스를 해결하기 위한 빠른 알고리즘이 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Birgin, E G; Lobato, R D; Morabito, R (2010). "An effective recursive partitioning approach for the packing of identical rectangles in a rectangle". Journal of the Operational Research Society. 61 (2): 306–320. doi:10.1057/jors.2008.141. S2CID 12718141.
  2. ^ Fowler, Robert J.; Paterson, Michael S.; Tanimoto, Steven L. (1981-06-13). "Optimal packing and covering in the plane are NP-complete". Information Processing Letters. 12 (3): 133–137. doi:10.1016/0020-0190(81)90111-3. ISSN 0020-0190.
  3. ^ Demaine, Erik D.; Demaine, Martin L. (2007-06-01). "Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity". Graphs and Combinatorics. 23 (1): 195–208. doi:10.1007/s00373-007-0713-4. ISSN 1435-5914.
  4. ^ a b Demaine, Erik (2015). "MIT OpenCourseWare – Hardness made Easy 2 – 3-Partition I". Youtube.{{cite web}}: CS1 maint :url-status (링크)
  5. ^ Huang, E.; Korf, R. E. (2013-01-23). "Optimal Rectangle Packing: An Absolute Placement Approach". Journal of Artificial Intelligence Research. 46: 47–87. doi:10.1613/jair.3735. ISSN 1076-9757.
  6. ^ "Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites". www.codeproject.com. Retrieved 2020-09-09.