Rechtecke in konvexe Polygone packen, aber ohne Rotationen

Ich interessiere mich für das Problem, identische Kopien von (zweidimensionalen) Rechtecken in ein konvexes (zweidimensionales) Polygon ohne Überlappungen zu packen. In meinem Problem dürfen Sie die Rechtecke nicht drehen und können davon ausgehen, dass sie parallel zu den Achsen ausgerichtet sind. Sie erhalten nur die Abmessungen eines Rechtecks ​​und die Eckpunkte des Polygons und werden gefragt, wie viele identische Kopien des Rechtecks ​​in das Polygon gepackt werden können. Wenn Sie die Rechtecke drehen dürfen, ist dieses Problem meines Erachtens NP-hart. Was ist jedoch bekannt, wenn Sie nicht können? Wie wäre es, wenn das konvexe Polygon einfach ein Dreieck ist? Gibt es bekannte Näherungsalgorithmen, wenn das Problem tatsächlich NP-schwer ist?

Bisherige Zusammenfassung (21. März '11). Peter Shor bemerkt, dass wir dieses Problem als eines der Quadrate der Verpackungseinheiten in einem konvexen Polygon betrachten können und dass dieses Problem in NP auftritt, wenn Sie ein Polynom auferlegen, das an die Anzahl der zu verpackenden Quadrate / Rechtecke gebunden ist. Sariel Har-Peled weist darauf hin, dass es für denselben polynomial begrenzten Fall ein PTAS gibt. Im Allgemeinen kann die Anzahl der gepackten Quadrate in Bezug auf die Größe der Eingabe, die nur aus einer möglicherweise kurzen Liste von Paaren von ganzen Zahlen besteht, exponentiell sein. Die folgenden Fragen scheinen offen zu sein.

Ist die vollständige unbegrenzte Version in NP? Gibt es ein PTAS für die unbegrenzte Version? Ist der polynomial begrenzte Fall in P oder NPC? Und mein persönlicher Favorit, ist das Problem einfacher, wenn Sie sich nur auf die Verpackungseinheit Quadrate in einem Dreieck beschränken?

Das Problem kann so umformuliert werden, dass eine maximale Anzahl von Punkten innerhalb eines konvexen Polygons ausgewählt wird, sodass jedes Paar (unter der -Metrik) mindestens 1 voneinander entfernt ist (man denke nur an die Zentren der Quadrate). . Dies hängt wiederum mit demselben Problem zusammen, bei dem man den regulären euklidischen Abstand verwendet. Dies hängt wiederum mit der Vernetzung zusammen, bei der es darum geht, ein Polygon in Bereiche mit gutem Verhalten zu unterteilen (dh Sie nehmen das Voronoi-Diagramm der Zentren [siehe Centroidal Voronoi tessellations]).$L_\infty$$1$

Wie auch immer, eine -Näherung ist ziemlich einfach. Sie schieben zufällig ein Raster der Seitenlänge O ( 1 / ϵ ) . Schneiden Sie das Polygon in das Gitter und lösen Sie das Problem innerhalb jedes Schnittpunkts des Polygons mit dem Gitter mit Gewalt. Ein Algorithmus mit Laufzeit O ( $(1-\epsilon)$$O(1/\epsilon)$ sollte leicht folgen, wobei M die Anzahl der Punkte (dh Rechtecke) und n o i s e ( ϵ $O(M*noise(\epsilon))$$M$$noise(\epsilon)$ist eine schreckliche Funktion, die nur von abhängt .$\epsilon$

Diese beiden Artikel befassen sich mit Ihrem Problem:

EG Birgin und RD Lobato, " Orthogonale Packung identischer Rechtecke innerhalb isotroper konvexer Regionen ", Computer & Industrial Engineering 59, S. 595-602, 2010. 

EG Birgin, JM Martínez, FH Nishihara und DP Ronconi, " Orthogonale Packung rechteckiger Elemente in willkürlichen konvexen Bereichen durch nichtlineare Optimierung ", Computers & Operations Research 33, S. 3535-3548, 2006.

Peter Shor stellte fest, dass dieses Problem durch eine Neuskalierung darin besteht, Quadrate von Einheiten in ein konvexes Polygon zu packen.

Bearbeiten: Der Rest dieser Antwort gilt nicht, da die explizit angegebene Anforderung, dass die zu verpackenden Formen alle dieselbe Größe haben, entfällt.

Die zugehörige Frage NP-Härte eines Sonderfalls eines orthogonalen Packungsproblems erwähnt ein Papier mit dem für die erste Frage erforderlichen Ergebnis:

• Quadrate in ein Quadrat packen , Joseph YT. Leung, Tommy W. Tam, Gilbert H. Young, CS Wong und Francis YL Chin, Journal of Parallel and Distributed Computing 10 271–275. ( Link )

Aus dem Papier:

Wir zeigen, dass das Problem der quadratischen Packung stark NP-vollständig ist, indem wir das 3-Partitions-Problem darauf reduzieren.

Daher ist das Problem selbst für den speziellen Fall, bei dem die zu verpackenden Rechtecke dem Behälter ähnlich sind , NP-hart . (Im Gegensatz zu den Autoren dieses Papiers bin ich nicht vollständig davon überzeugt, dass das Problem in NP liegt, da die Positionen möglicherweise mit großer Genauigkeit angegeben werden müssen, was dazu führen kann, dass die Überprüfung in der Eingabegröße nicht mehr polynomisch ist. )

Vielleicht kann dieses Papier für Sie von Interesse sein:

Kacheln eines Polygons mit Rechtecken von Kenyon & Kenyon in FOCS 92.

Wenn das Polygon, in das Sie packen möchten, nicht unbedingt konvex ist, wird das Problem meiner Meinung nach NP-schwer. Hier ist ein sehr lückenhafter Beweis. Die Reduzierung ist auf ein Problem vom Typ Planar-3-SAT zurückzuführen. Für jede Variable können Sie eine Stelle von 1,1 x 1 festlegen. Je nachdem, wo Sie in diesem Bereich ein Quadrat platzieren, wird bestimmt, ob Ihre Variable wahr oder falsch ist. Wenn Sie einen Bereich links / rechts verlassen, können Sie zwei weitere Felder etwas weiter nach innen und die dahinter verschieben, um schließlich einen weiteren, freien Platz an einer anderen Stelle zu schaffen, die jetzt zusammen vier Felder und so weiter betrifft. Nachdem Sie so viele Kopien haben, wie das jeweilige Literal vorkommt, verbinden Sie diese Röhren mit der jeweiligen Klauselkomponente und verwenden dort wieder ein ähnliches Gadget, um sicherzustellen, dass von den drei eingehenden Röhren mindestens eine 0,1 zusätzlichen Platz benötigt.