Rechtecke in konvexe Polygone packen, aber ohne Rotationen

23

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?

Raphael
quelle
Packen mit 1x3-Rechtecken ist NP-vollständig (mit Drehung) und ich denke, es wird einfach, wenn wir Drehungen nicht zulassen. Sie ermitteln die maximale Anzahl von Rechtecken für jede Zeile (oder Spalte) und addieren sie, um die maximale Gesamtanzahl gepackter Rechtecke zu erhalten.
Mohammad Al-Turkistany
Ich bin mir nicht sicher, ob das Fixieren der Abmessungen auf 1x3 (oder etwas anderes) zu viel für mein Problem hilft, oder? Das konvexe Polygon muss keine zu den Achsen parallelen Seiten haben, und Sie müssen immer noch entscheiden, wo die Rechtecke platziert werden sollen. Sie könnten sie zuerst auf der y-Achse am niedrigsten platzieren und dann als sinnvolle Heuristik linksbündig ausrichten, aber Sie können ziemlich einfach Beispiele konstruieren, bei denen dies nicht optimal ist.
Raphael
9
Sie können eine affine Transformation anwenden, um alle Rechtecke erstellen . Das Problem ist also gleichbedeutend mit dem Packen von Quadraten. 1×1
Peter Shor
1
@turkistany: Würden Sie mir einen Hinweis geben, der die NP-Vollständigkeit für 1x3-Rechtecke zeigt? Oder ist es leicht zu beobachten?
Yoshio Okamoto
3
Durch die Suche basierend auf Peter Shors Beobachtung kommt maven.smith.edu/~orourke/TOPP/P56.html zum Vorschein , was interessant ist. Es scheint sich jedoch auf allgemeine einfache Polygone zu konzentrieren (dh sie können konkav sein).
Raphael

Antworten:

12

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]).L1

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 ( M(1ϵ)O(1/ϵ) sollte leicht folgen, wobei M die Anzahl der Punkte (dh Rechtecke) und n o i s e ( ϵ ) ist.O(Mnoise(ϵ))Mnoise(ϵ)ist eine schreckliche Funktion, die nur von abhängt .ϵ

Sariel Har-Peled
quelle
Vielen Dank. Habe ich Recht zu denken, dass selbst in dem Fall, in dem wir ein Polynom an die Anzahl der Rechtecke / Quadrate gebunden haben, es immer noch nicht klar ist, ob das Problem in P liegt?
Raphael
1
Hier sind meine 2 Cent zum Erraten / Spekulieren ... Es wäre überraschend, wenn es in P wäre - Sie müssten einige zusätzliche Eigenschaften der optimalen Lösung zeigen. Ich würde jedoch davon ausgehen, dass ein formaler Nachweis der NP-Härte unerreichbar ist - das Problem ist zu strukturiert. Feder und Greene zeigten, dass die k-Zentren-Clusterung innerhalb eines bestimmten Faktors nur schwer zu approximieren ist. Ich denke / spekuliere, dass ihr Beweis verwendet werden kann, um zu beweisen, dass das obige Problem NP-schwer ist, wenn das Polygon Löcher hat ...
Sariel Har-Peled
2

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.

 

Marcus Ritt
quelle
Diese Artikel befassen sich mit der Lösung des Problems in der Praxis. Soweit ich das beurteilen kann, stellt sich die Frage, ob bekannt ist, dass das Problem NP-schwer ist.
András Salamon
3
Es ist ziemlich einfach zu zeigen, dass es in NP ist. Angenommen, ich gebe Ihnen ein Diagramm der optimalen Packung, aus dem hervorgeht, welche Quadrate welche Seiten des Polygons berühren und welche Quadrate über / unter / links / rechts von anderen Quadraten liegen. Die Frage, ob Sie die Koordinaten für eine Menge von Quadraten finden können, die genau so packen, ist ein lineares Programm, und Sie können überprüfen, ob dies ein Diagramm für eine durchführbare Packung ist.
Peter Shor
4
Wenn alle Eckpunkte Ihres Polygons Ganzzahlen (oder Rationen) sind, besagt ein Standardergebnis in linearen Programmen, dass Sie nicht mehr als ein Polynom mit zusätzlicher Genauigkeit benötigen, und das lineare Programm kann exakt in Polynomzeit gelöst werden. Entschuldigung, wenn Sie das bereits gewusst haben, aber ich kann es Ihrem obigen Kommentar nicht entnehmen - und selbst wenn Sie es getan haben, werden es einige Leute nicht.
Peter Shor
2
Vielen Dank. Ich wusste das einmal, aber es war gut, daran erinnert zu werden. Es scheint auch, dass Sie eine exponentielle Anzahl von Quadraten im Polygon haben könnten, also bin ich mir nicht sicher, ob Sie es sich leisten können, sie alle aufzulisten. Vielleicht gibt es eine Skalierung, die Sie tun können, um das zu umgehen?
Raphael
3
@Rafael: Ich habe (ohne Begründung) angenommen, dass Sie ein Polynom für die Anzahl der Quadrate haben. Wenn Sie Polygone mit exponentieller Größe zulassen, werden die Dinge viel schwieriger.
Peter Shor
1

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. )

András Salamon
quelle
5
Betrachtet man das Papier, so ergibt sich aus den Diagrammen, dass die zu verpackenden Quadrate nicht alle gleich groß sind.
Peter Shor
1
@ Peter: Sie haben recht, dieses Papier beinhaltet nichts über Raphaëls Problem.
András Salamon
0

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

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

Sylvain Peyronnet
quelle
Vielen Dank. Wenn ich das jedoch richtig verstehe, deckt eine Kachelung das Polygon genau ab. Dies wird in meinem Fall fast nie möglich sein (man betrachte ein beliebiges Dreieck bei einer beliebigen Orientierung), was mein Optimierungsproblem grundlegend anders zu machen scheint.
Raphael
in der Tat ist dies nicht das gleiche Problem, mein Fehler.
Sylvain Peyronnet
0

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.

domotorp
quelle
1
Das klingt plausibel. Beachten Sie, dass Raphaël einen Link in einem Kommentar maven.smith.edu/~orourke/TOPP/P56.html mit einem Zeiger auf ein Papier mit der tatsächlichen Verkleinerung bereitgestellt hat .
András Salamon
Oh, ich habe es nicht bemerkt, danke.
Domotorp