Wie komplex ist das Packen von Rechtecken, wenn Rotationen zulässig sind?

In dem Rechteck Packungsproblem wird man eine Menge von Rechtecken gegeben und begrenzende Rechteck R . Die Aufgabe besteht darin, eine Platzierung von r 1 , … , r n innerhalb von R so zu finden, dass sich keines der n Rechtecke überlappt. Im Allgemeinen ist die Ausrichtung jedes Rechtecks r i fest. Das heißt, die Rechtecke können nicht gedreht werden. In diesem Fall ist bekannt, dass das Problem NP-vollständig ist (siehe z. B. Korp 2003 ).$\{r_1,\dots,r_n\}$$R$$r_1,\ldots,r_n$$R$$n$$r_i$

Wie komplex ist das Problem beim Packen von Rechtecken, wenn Rechtecke um Grad gedreht werden können ?$90$

Intuitiv sollte das Ermöglichen von Rotationen das Problem nur erschweren, da man zuerst eine Ausrichtung für jedes Rechteck auswählen und dann das Problem des Packens ohne Rotation lösen sollte. Der NP-Härtenachweis für den Fall ohne Rotation ist jedoch eine Reduzierung gegenüber der Behälterpackung und scheint entscheidend von der festen Ausrichtung jedes Rechtecks ​​abzuhängen, um die Behälter zu konstruieren. Für den Fall, dass Drehungen erlaubt sind, konnte ich keinen entsprechenden NP-Härtenachweis finden.

Wir können das Problem des Packens ohne Drehung auf das Problem des Packens mit erlaubter Drehung wie folgt reduzieren. Nehmen Sie eine beliebige Instanz des Problems der Nichtrotation. Vertikal skaliert die gesamte Instanz um die doppelte Verhältnis der kleinsten Breite eines Rechtecks R i durch die Höhe der Behälter Rechteck geteilt R . (Dieses Verhältnis hat eine Polynomzahl von Bits, so dass die Transformation in Polynomzeit ausgeführt werden kann.) Jedes skalierte Rechteck r $(R, r_1, r_2, \dots, r_n)$$r_i$$R$ passtnur in seiner ursprünglichen Ausrichtungin den skalierten Behälter R ' , sodass durch Drehen keine neuen Lösungen entstehen.$r'\!\!_i$$R'$