기요틴 절단

기요틴 절단은 기요틴 절삭만을 사용하여 주어진 큰 직사각형 시트에서 고정 치수의 작은 직사각형 품목을 생산하는 과정이다.단두대 절단(edge-to-edge cut이라고도 함)은 종이 단두대와 비슷하게 기존 직사각형의 한쪽 가장자리에서 반대쪽 가장자리로 가는 직선 이등분선이다.

기요틴 절단술은 특히 유리 산업에서 흔하다.유리 시트는 수평선과 수직선을 따라 점수가 매겨지고, 그 선을 따라 깨져 더 작은 패널을 얻는다.^[1]철판을 자르고, 가구를 만들기 위해 목판을 자르고, 판지를 상자로 자르는 데도 유용하다.^[2]

단두대 절단과 관련된 다양한 최적화 문제가 있는데, 이를테면 생산되는 조각의 총 면적 또는 그 총가치를 최대화한다거나, 대형 시트의 폐기물(미사용 부품)의 양 또는 총 시트 수를 최소화한다.그들은 조합 기하학, 운영 연구, 산업 공학에서 연구되어 왔다.^[3]

연관성이 있지만 다른 문제는 단두대 파티션이다.그 문제에서 작은 직사각형의 치수는 미리 고정되어 있지 않다.이 도전은 원래 시트가 직사각형이 아닐 수 있다는 사실에서 비롯된다. - 그것은 직선으로 된 다각형이 될 수 있다.특히, 구멍(원료의 결함을 나타내는 결함)을 포함할 수 있다.최적화 목표는 대개 작은 직사각형의 수를 최소화하거나 절단부의 총 길이를 최소화하는 것이다.

용어 및 가정

단두대 절단에 관한 문헌에는 다음과 같은 용어와 공명이 자주 사용된다.

• 주식 시트라고도 불리는 큰 직사각형은 잘라야 할 생 직사각형 시트다.문제의 주요 입력인 폭 W와₀ 높이 H가₀ 특징이다.
• 항목이라고도 하는 작은 직사각형은 절삭에 필요한 출력물이다.그것들은 폭이 w와_i 높이 h로_i 특징지어지며, 1,...,m에서 m은 직사각형의 수이다.흔히 같은 치수의 직사각형을 여러 개 가질 수 있게 되는데, 이 경우 치수 쌍(w_i,h_i)을 유형이라고 한다.
• 흔히 정의 패턴이라고 불리는 커팅 패턴은 주식 시트에 작은 직사각형이 배열된 것이다.점(x_i,y_i)의 순서로 주어질 수 있는데, 여기서 (x_i,y_i)는 직사각형 i의 왼쪽 하단 좌표다.이러한 패턴에서 직사각형 i는 수평 세그먼트(x_i, x_i+w_i)와 수직 세그먼트(y_ii, y+h_i)를 차지한다.
• 빌드는 두 개의 작은 직사각형을 붙여 새로운 직사각형을 만드는 것을 말한다.단두대 구속조건으로 인해, 두 가지 유형의 빌드만 있다: 수평 빌드에서는 결합 직사각형의 너비가_i w+w와_j 높이 최대(h_i,h_j)이고, 수직 빌드에서는 결합 직사각형의 너비가 최대(w_i,w_j)와 높이_i h+h이다_j.모든 패턴은 반복적인 빌드 순서로 표현될 수 있다.빌드의 모든 재귀 순서는 등가의 결합 구조를 가진 많은 다른 패턴에 대응한다; 동일한 재귀 빌드에 해당하는 모든 패턴의 집합을 단두대 절단 클래스라고 한다.^[4]

일부 문제는 아래에 설명된 바와 같이 추가 입력을 허용한다.목표는 원시 직사각형에서 목표 치수를 가진 작은 직사각형을 자르는 것이다.흔히 다음과 같은 가정을 한다.^[2]

• 모든 절단은 폭이 0이다.이것은 큰 일반성을 잃지 않는데, 각 절삭의 폭이 d>0이면 0, ...,m에서 i에 대해 w와_i h에_i d를 추가하기만 하면 문제가 영폭변형으로 줄어들 수 있기 때문이다.
• 대상 치수는 회전할 수 없다. 즉 w-by-h가 h-by-w와 같은 유형이 아니다.직사각형을 회전할 수 있는 변종은 회전 패턴을 명시적으로 추가하면 회전할 수 없는 변종으로 줄일 수 있기 때문에 이것은 그다지 일반성을 잃지 않는다.

지정된 패턴 확인

패턴 검증 문제에는 점의 순서_i(x_i,y)로 주어진 절단 패턴이 있는데, 여기서 (x_i,y_i)는 직사각형 i의 왼쪽 하단 좌표(각 대상차원 직사각형)이다.단두대 절단만을 이용해 이 패턴을 구현할 수 있는지 여부를 결정하고, 그렇다면 그런 절단 순서를 찾는 것이 목표다.

분명한 필요 조건은 두 개의 입력 사각형이 두 치수에서 겹치지 않는다는 것이다.벤 메사우드, 청빈, 에스피노우스가^[5] 더 강한 조건을 제시하는데, 이는 필요하고도 충분하다.이 입력은 사각형 왼쪽에서, x1 ≤ 그러한 왼쪽에서 오른쪽으로 명령을 받았다...≤ xm다. 그런, 이 치환과, 사각형 아래쪽부터 충전할 주문할 한가지 순열 p지수에, 즉, yp(1)≤...≤ yp(m).4지수를 감안할 때 i1≤ i2과j1 ≤ j2 이번 세트 E(i1,i2,j1,j2)을 포함하는 지수의 모든 사각형의 bottom-left 구석이 있다.에 월.e 사각형 [x_i1,x_i2] X [y_p(j1),y_p(j2)]절삭 패턴은 모든₁ 지수 i j₂₁ i와 j ≤ j에₂ 대해 다음 조건 중 적어도 하나가 E(i₁,i₂,i,j₁,j₂)에 대해 충족되는 경우에만 단두대 패턴이다.

1. E(i₁,i₂,j₁,j₂)는 최대 하나의 요소를 포함한다.
2. E(i₁,i₂,j₁,j₂)의 모든 I에 걸쳐 수평 세그먼트(x_i,x_i+w_i)의 결합은 최소 두 개의 분리 간격으로 구성된다.
3. E(i₁,i₂,j₁,j₂)의 모든 I에 걸쳐_i 수직 세그먼트(y_i, y+h_i)의 결합은 최소 두 개의 분리 간격으로 구성된다.

조건 2는 E(i₁,i₂,j₁,j₂)의 직사각형은 수직 절단(두 개의 분리 수평 간격 사이를 이동)으로 분리될 수 있음을 의미하며, 조건 3은 E(i₁,i₂,j₁,j₂)의 직사각형은 수평 절단로 분리될 수 있음을 의미한다.모든 조건은 인접한 직사각형 집합이 둘 이상의 원소를 포함할 경우, 단두대를 절단하여 분리할 수 있다는 것을 의미한다.

이 조건은 다음과 같은 알고리즘으로 확인할 수 있다.

• 각 반복 시, 최소 두 개의 직사각형을 포함하는 주어진 패턴을 단두대 절단을 사용하여 두 개의 분리형 하위 패턴으로 나누고 각 하위 패턴에 반복한다.
• 모든 하위 패턴이 하나의 직사각형을 포함하거나(이 경우 대답은 "예"), 더 이상 단두대 자르기(이 경우 "아니오")가 불가능할 때 중지한다.

주어진 패턴에 대해 단두대를 절단한 것을 찾아내는 것은 다음과 같다.

• m 수평 간격을 정하여 왼쪽에서 오른쪽으로 정렬하고, m 수직 간격을 정하여 아래에서 위로 정렬한다.O(m log m) 시간이 걸린다.
• 겹치는 수평 간격을 병합하고 겹치는 수직 간격을 병합하십시오.이것은 시간이 걸린다.
• 병합 후 최소 두 개의 분리 수평 간격이 있을 경우 수직 단두대 절단, 두 개의 분리 수직 간격이 있을 경우 수평 절단, 그렇지 않을 경우 절단이 불가능하다.

주문 단계는 1회, 병합 단계는 m-1회 실시된다.따라서 전체 알고리즘의 런타임은 O(m²)이다.

알고리즘이 "예"를 반환하면, 일련의 단두대 절단도 생성되고, "아니오"를 반환하면 단두대 절단으로는 분리할 수 없는 특정 직사각형 하위 집합도 생성된다.

단두대-스트립 절단 문제를 혼합 정수 선형 프로그램으로 제시하기 위해 필요하고도 충분한 조건을 사용할 수 있다.^{[5]: sec.5} 이들의 모형은 3n⁴/4개의 이항변수와 2n⁴ 제약조건이 있으며, 실질적으로 유용하지 않은 것으로 간주된다.

최적의 절단 패턴 찾기

이것들은 2차원 절삭 재고, 빈 패킹, 직사각형 포장 문제의 변형이며, 절삭은 단두대 절삭이 될 수 밖에 없다.^[6]

• 기본(무가중량) 단두대 절단 문제에서 필요한 출력은 단두대를 잘라 목표 치수의 조각을 생성하는 시퀀스로, 생산되는 조각의 전체 면적을 최대화한다(동일하게, 원 직사각형의 폐기물을 최소화한다).
• 가중치 변종에서는 각 대상 차원 i에 대해 값 v도_i 있다.그 다음, 생산한 작품의 총 가치를 극대화하는 것이 목표다.비가중(폐소-소모화) 변종은 각 표적-임금의 값이 해당 면적(v_i = h_i * w_i)과 같게 하여 가중변형으로 줄일 수 있다.
• 제한된 변형에서, 각 대상-차원 i에 대해, 해당 유형으로 생산될 수 있는 조각 수에 상한_i b가 있다.
  • 이중 구속 변형에서, 각 대상-차원 i에 대해, 생산된 조각의 수에는 하한 a와_i 상한 b가_i 모두 있다.
• 이항변형은 각 표적 치수가 최대 한 번 나타나야 하는 제한된 변종이다(즉, 상한은 1이다).이 경우는 의사결정 문제와 관련이 있는데, 여기서 단두대 절단을 이용하여 각 목표 차원의 단일 요소 생산이 가능한지 여부를 결정하는 것이 목표다.^[4]
• 단두대 스트립 컷팅 문제에서 큰 직사각형은 높이가 무한대(단, 고정 너비)로 되어 있으며, 사용한 총재질(동등하게, 전체 높이)을 최소화할 수 있도록 각 타입의 단일 직사각형을 절단하는 것이 목표다.2차원 스트립 패킹 문제의 변형이다.
• 주식최소화 문제에서는 동일 차원의 주식 시트가 무한정 존재하며, 가능한 한 적은 수의 시트를 사용하여 필요한 모든 목표 직사각형을 자르는 것이 목표다.^[5]2차원 빈포장 문제의 변종이다.^[7]
• k-16 단두대 커팅은 단두대 커팅의 제한된 변형이다. 단두대 커팅은 1단계에서는 수평 커팅만, 2단계에서는 수직 커팅만 이루어진다.
  • 2단계 변종에서, 1단계에서 발생한 모든 스트립이 동일한 위치(1-그룹이라고 함)에서 절단되는지(2-그룹이라고 함) 또는 가능한 다른 위치("자유"^[8]라고 함)에서 절단되는지가 더 구별된다.
• 1-165단두대 절단은 각 절단이 하나의 직사각형을 분리하는 제한적인 단두대 절단의 변형이다.
  • 2단 단두대 절단은 각 부분 자체가 1단절 패턴이 되도록 1단절 패턴으로, p단순 절삭 패턴을 재귀적으로 정의할 수 있다.^[9]

최적화 알고리즘

한 가지 유형(즉, 모든 대상 직사각형이 동일하고 방향이 동일)만 있는 특수한 경우를 단두대 팔레트 적재 문제라고 한다.타르노프스키, 테르노, 셰이타우어는^[10] 이를 해결하기 위한 다항식 시간 알고리즘을 제시한다.

단, 2종 이상일 경우 단두대 절단 관련 최적화 문제는 모두 NP 하드다.그 실질적인 중요성 때문에, 다양한 정확한 알고리즘과 근사 알고리즘이 고안되었다.

• 길모어와 고모리는^[11][12] 무대의 단두대 절단을 위한 역동적인 프로그래밍 재귀성을 선보였다.그러나 두 알고리즘 모두 오류가 있는 것으로 나중에 밝혀졌다^[13][2].비즐리는^[2] 정확한 다이매닉 프로그래밍 알고리즘을 제시했다.
• 헤르츠와^[13] 크리스토피데스, 휘트록은^[14] 무제한 단두대 절단을 위한 나무 탐색 절차를 제시했다.
• 마스든과^[15] 왕 교수는^[16] 휴리스틱한 알고리즘을 제시했다.
• 히피, 음할라, 사디는^[6] 이중으로 구속되는 단두대 절단 문제에 대한 알고리즘을 제안한다.Best-first search를 이용한 bottom-up bound and bound 알고리즘이다.
• Clautiaux, Jouglet, Moukrim은^[4] 의사결정 문제에 대한 정확한 알고리즘을 제안한다.그들의 알고리즘은 기요틴 절단 패턴 클래스의 콤팩트한 표현을 사용하며, 그들이 기요틴 그래프라고 부르는 지시된 그래프를 사용한다.이 그래프의 각 호는 "수평" 또는 "수직"의 두 가지 색상 중 하나로 색칠된다.이 그래프의 각 단색 지시 주기는 빌드에 해당한다.단색 주기를 반복적으로 수축함으로써 절단 패턴 클래스를 나타내는 반복적인 빌드시퀀스를 회복할 수 있다.모든 단두대-그래프에는 m과 2m-2 호 사이의 호가 들어 있다.일반 기요틴 그래프라고 불리는 특별한 종류의 기요틴 그래프는 독특한 해밀턴 회로를 포함하는 흥미로운 특성을 가지고 있다.이 회로에 따라 정점을 정렬하면 그래프가 잘 정렬된 일반 단두대 그래프가 된다. 이러한 그래프와 절단 패턴 클래스 사이에는 일대일 일치성이 있다.그런 다음 잘 정렬된 일반 단두대 그래프의 공간에 제약 프로그래밍을 사용하여 최적화 문제를 해결한다.
• 루소, 보치아, 스포르차, 스털은^[8] 가중치와 가중치가 없는 제한적 단두대 절단(양적 상위 분지 포함)을 다루는 90개 이상의 논문을 검토한다.정확한 솔루션에는 동적 프로그래밍과 트리 검색(지점 및 바인딩)의 두 가지 주요 접근방식이 있다.트리 검색 접근법은 상향식(단일 직사각형부터 시작해서 빌드를 사용하여 전체 시트를 구성) 또는 하향식(top-down)으로 추가로 분류된다.모든 접근방식에서, 검색 공간을 효율적으로 다듬기 위해서는 좋은 하한과 상한을 찾는 것이 중요하다.이러한 한계는 종종 제한되지 않은 변형, 단계적 변형 및 비구두 변형과 같은 관련 변형에 대한 해결책에서 나온다.
• 아보 음사바, 슬마네, 아흐메드 리아드 바바알리."직교 절단 문제에 대한 향상된 유전 알고리즘과 결합된 새로운 단두대 배치 휴리스틱." 2011 IEEE 국제 산업 공학 및 엔지니어링 관리 회의IEEE, 2011.
• 아보 음사바, 슬마네, 아흐메드 리아드 바바알리, 바스마 사거."직교 절단-재고 문제를 위한 새로운 BLF2G 기요틴 배치 휴리스틱으로 제어된 안정성 유전 알고리즘"국제 인지 정보 및 자연 지능 저널 (IJCINI) 13, No. 4(2019): 91-111.

구현

• McHale과 Shah는^[17] 언제든 알고리즘을 구현하는 Prolog 프로그램을 작성했다: 주어진 시간 내에 대략적으로 최적의 솔루션을 생성한 다음 사용자가 더 많은 시간을 허용할 경우 이를 개선한다.이 프로그램은 한 전문 제지업체가 사용했으며, 종이 레이아웃에 필요한 시간을 줄이면서도 낭비를 줄였다.

기요틴 분리

기요틴 분리는 입력부가 비행기에서 n쌍이 분리되는 볼록한 물체의 집합인 관련 문제로, 일련의 기요틴 절단 과정을 이용해 분리하는 것이 목표다.분명히 그들 모두를 분리하는 것은 가능하지 않을 수도 있다.호르헤 우루티아 갈리시아는 그것들 중 일정한 부분을 분리할 수 있는지, 즉 그러한 크기 n의 어떤 집합에서 단두대 분리 가능한 크기 cn의 하위 집합이 존재하는지를 물었다^[18].

파흐와 타도스는^[19] 다음과 같이 증명했다.

• 만약 모든 물체의 크기가 비슷하다면, 그 중 일정 부분을 분리할 수 있다.Formally, if all objects contain a circle of radius r and are contained in a circle of radius R, then there is a separable set of size ${\displaystyle {\frac {\pi r^{2}}{128R^{2}}}n\approx {\frac {1}{40.7(R/r)^{2}}}n}$. Proof: construct a grid with cell size 8R by 8R.그리드를 임의로 균일하게 이동시킨다.각 물체는 확률 1/4을 가진 수평선과 교차하며 확률 1/4을 가진 수직선과도 교차하므로 교차하는 물체의 예상 수는 $n{\displaystyle }$ / ${\displaystyle n/2}$이다. 따라서$,$ 최대 $n{\displaystyle }$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle n/$2}$개의$물체에$$ 교차하는 격자선이 존재한다.각 그리드 셀의 면적은${\displaystyle }$(${\displaystyle 8}$ R${\displaystyle {}^{}}$) ${\displaystyle {2\mathrm{}}^{}}$ ${\$이고, 각 물체의 면적은 적어도 ${\displaystyle {}^{}}$ r ${\displaystyle {2\mathrm{}}^{}}${\$displaystyle \pi$ r$^{2$}}, 각 셀은 최대${\displaystyle \frac{}{}}$(${\displaystyle \frac{8}{}}$ ${\displaystyle \frac{R{}^{}}{}}$) ${\displaystyle \frac{{2\mathrm{}}^{}}{}}$ ${\displaystyle \frac{{}^{}}{}}$ ${\displaystyle \frac{{}^{}}{}}$ ${\displaystyle \frac{{2\mathrm{}}^{}}{}}$ ${\pi r^{{R)2}}개$의 물체를$$ 포함한다$.$각 셀에서 하나의 개체를 선택하고 동일한 셀의 다른 개체와 분리하십시오.The total number of objects separated in this way is at least ${\displaystyle {\frac {n}{2}}/{\frac {(8R)^{2}}{\pi r^{2}}}={\frac {\pi r^{2}}{128R^{2}}}n.}$ A similar argument for the case of unit squares gives ${\displaystyle {\frac {1}{27}}n$$.}$
• 객체가 직선 세그먼트인 경우, 경우에 따라 최대 $O{\displaystyle ({}^{}}$ ${\displaystyle {{\log }_{}}^{}}$ ${\displaystyle {{3\mathrm{}}_{}}^{}}$ ${\displaystyle {{}_{}}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle \approx }$ ${\displaystyle O(n^{}}$ 0$){\displaystyle O(n^{\log _{3}{2}})\약간$의 $O(n^{0.63})$만 분리할 수 있다.특히 모든 양의 정수 k에 대해 최대 $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle k^{}}$ ${\$$displaystyle 3^{k}$의 분리$$ 간격으로 3 ${\displaystyle k^{}}$ ${\$$displaystyle 2^{k}$가 분리될$$ 수 있는 패밀리가 있다.
• n 볼록한 물체의 어떤 집합에서도 적어도 $\Omega {\displaystyle \mathrm{}}$(${\displaystyle {n\mathrm{}}^{}}$ 1${\displaystyle {}^{}}$/ 3${\displaystyle {}^{}}$) ${\displaystyle \Oomega (n^{1/3})$는 분리할 수 있다$$.
• n개의 직선 세그먼트 모음에서 최소 $\Omega {\displaystyle \mathrm{}({}^{}}$ ${\displaystyle {1\mathrm{}}^{}}$/ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle \Oomega(n^{1/2})$를 분리할 수 있다$$.그들은 최악의 경우를 선분할을 통해 얻을 수 있다고 추측한다.
• n축-병렬 직사각형 집합에서 최소한 $n{\displaystyle }$/${\displaystyle }$( 2 ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle$ n$/(2\log {n})$를 분리할 수 있다$$.그들은 $\Omega {\displaystyle \mathrm{}}$(${\displaystyle n}$) ${\displaystyle \Oomega (n)}$이(가) 분리될 수 있다고$$ 추측한다. 이 추측은 여전히 열려 있다.
• 모든 R-지방 개체 모음(디스크 포함 최소 크기는 최대 R배임)에서 $최소한{\displaystyle }$ n${\displaystyle }$/ (${\displaystyle c}$ R 로그${\displaystyle nn}$ ${\displaystyle )}$ ${\displaystyle$ n$/(c_{R}\log {n}})$ 개체를$$ 저장할 수 있으며, 여기서 ${\displaystyle C_{}}$ ${\$는 R에만 의존하는 상수다.
  • 유사한 정리는 더 높은 차원에서도 유효하다: 분리 가능한 객체의 수는${\displaystyle }$n / ${\displaystyle c}$( R${\displaystyle }$,${\displaystyle d}$ )${\displaystyle d^{}}$ ${\$이다$.$
• 이러한 모든 분리 가능한 하위 패밀리는 $시간{\displaystyle }$ O${\displaystyle (n}$ ${\displaystyle \log }$ $){\displaystyle$ O$(n\log {n})$로 구성할 수 있다$.$ 개체가 전체적으로 N면이 있는 다각형인 경우, 구분선은 $시간{\displaystyle }$ O${\displaystyle (N}$+ ${\displaystyle n}$ ${\displaystyle \log }$ $){\displaystyle$ O$(N+n\log {n})$로 계산할 수 있다$.$

아벳, 찰렘수크, 코레아, 카르렌바우어, 페레스란테로, 소토, 비제^[20] 등이 다음과 같이 증명하였다.

• n축-병렬 단위 제곱의 어떤 집합에서도 최소한 n/2를 분리할 수 있으며, 최대 n/2를 분리할 수 있는 경우가 있다.
• n축-병렬 제곱의 어떤 집합에서도 최소한 n/81은 분리할 수 있다.
• 가중치가 있는 n축 평행 정사각형 집합에서는 총 중량의 최소 4/729를 분리할 수 있다.
• 가중치가 있는 n축 평행 d차원 입방체의 모든 집합에서 전체 중량의${\displaystyle }1{\displaystyle \mathrm{}}$/$2$ O${\displaystyle {}^{}}$( d$){\$ 스타일 1/$^{O(d)}}}$을(를) 분리할 수 있다.
• 별도의 $\Omega {\displaystyle \mathrm{}(n}$) ${\displaystyle \Oomega(n)}$축-병렬$$ 직사각형이 가능한 것으로 추측되는 것에 대해, 그들이 정합하지 않는 한, O(${\displaystyle {}^{}{5\mathrm{}}^{}}$) ${\displaystyle O(n^{}$$5$)의 축-병렬 직사각형 최대 분리 집합 문제에 대한 O(1) 근사 알고리즘을 의미한다는 것을 보여준다.$)}$.

칸과 피투는^[21] 다음과 같이 증명했다.

• n축 평행 직사각형에서는 o${\displaystyle (}로그{\displaystyle \log }$ log${\displaystyle \mathrm{logn}}$) ${\displaystyle o(\log \log n)}$단계만$$ 허용되면 $\Omega {\displaystyle \mathrm{}(n}$) ${\displaystyle \Oomega(n)}$직사각형을$$ 분리할 수 없다.
• 직사각형이 가중될 때 $o{\displaystyle (\log logn}$/ ${\displaystyle \log }$ ${\displaystyle }$ ${\displaystyle \log }$ ⁡ log ${\displaystyle n}$) ${\displaystyle o(\log {n}/\log \log \n})$ 단계만$$ 허용되면 중량의$$ $\Omega {\displaystyle \mathrm{}(n}$)$${\$displaystysty \Oomega(n)}$을(n) 분리할 수 없다.
• $n{\displaystyle }$/${\displaystyle }$( ${\displaystyle 1}$+ ${\displaystyle \log }$ $){\displaystyle n/(1+\log {n})$ 직사각형을$$ 구분하는 간단한 2단계 알고리즘이 있다.
• 모든 지방 직사각형 모음에서 $\Omega {\displaystyle \mathrm{}(n}$) ${\displaystyle \Oomega(n)}$을(를) 분리할 수 있다$$.
• n축-병렬 제곱의 어떤 집합에서도 최소한 n/40은 분리할 수 있다.
• 가중치가 있는 n축 평행 정사각형 집합에서는 총 중량의 1/80 이상을 분리할 수 있다.

참고 항목:

• 기하분리기
• 하이퍼플레인 분리 정리

더 많은 변종류

최근에 연구된 문제의 일부 변형에는 다음이 포함된다.

• 3차원의 기요틴 절단.^[22][23]
• 원직사각형에 결함이 있을 수 있지만 생산된 직사각형은 결함이 없어야 한다.^[24]

참조

아보 음사바, 슬마네, 아흐메드 리아드 바바알리."직교 절단 문제에 대한 향상된 유전 알고리즘과 결합된 새로운 단두대 배치 휴리스틱." 2011 IEEE 국제 산업 공학 및 엔지니어링 관리 회의IEEE, 2011.