Emballage de rectangles dans des polygones convexes mais sans rotation

23

Je m'intéresse au problème d'emballer des copies identiques de rectangles (2 dimensions) dans un polygone convexe (2 dimensions) sans chevauchements. Dans mon problème, vous n'êtes pas autorisé à faire pivoter les rectangles et pouvez supposer qu'ils sont orientés parallèlement aux axes. On vous donne simplement les dimensions d'un rectangle et les sommets du polygone et vous avez demandé combien de copies identiques du rectangle peuvent être regroupées dans le polygone. Si vous êtes autorisé à faire pivoter les rectangles, ce problème est connu pour être NP-difficile, je crois. Cependant, que sait-on si vous ne le pouvez pas? Et si le polygone convexe n'était qu'un triangle? Existe-t-il des algorithmes d'approximation connus si le problème est en effet NP-difficile?

Résumé jusqu'à présent (21 mars '11). Peter Shor observe que nous pouvons considérer ce problème comme l'un des carrés d'unité d'emballage dans un polygone convexe et que ce problème est dans NP si vous imposez une limite polynomiale au nombre de carrés / rectangles à emballer. Sariel Har-Peled fait remarquer qu'il existe un PTAS pour le même cas borné polynomialement. Cependant, en général, le nombre de carrés emballés peut être exponentiel dans la taille de l'entrée qui ne se compose que d'une liste éventuellement courte de paires d'entiers. Les questions suivantes semblent être ouvertes.

La version complète sans limite est-elle en NP? Existe-t-il un PTAS pour la version illimitée? Le cas est-il polynomialement borné en P ou NPC? Et mon préféré, le problème est-il plus facile si vous vous limitez à emballer les carrés d'unité dans un triangle?

Raphael
la source
L'emballage avec des rectangles 1x3 est NP-complet (avec rotation) et je suppose que cela devient facile si nous interdisons les rotations. Vous trouvez le nombre maximum de rectangles pour chaque ligne (ou colonnes) et les ajoutez pour obtenir le nombre maximum global de rectangles compressés.
Mohammad Al-Turkistany
Je ne suis pas sûr que fixer les dimensions à 1x3 (ou autre chose) aide trop à mon problème, n'est-ce pas? Le polygone convexe n'a pas nécessairement de côtés parallèles aux axes et vous devez toujours décider où placer les rectangles. Vous pouvez les placer le plus bas dans l'axe des y puis les justifier à gauche comme une heuristique raisonnable, mais vous pouvez construire des exemples assez facilement là où ce n'est pas optimal.
Raphael
9
Vous pouvez appliquer une transformation affine pour rendre tous les rectangles . Le problème est donc équivalent à celui des carrés d'emballage. 1×1
Peter Shor
1
@turkistany: Pourriez-vous me donner une référence qui montre l'exhaustivité NP pour les rectangles 1x3? Ou est-ce facile à observer?
Yoshio Okamoto
3
En cherchant sur la base de l'observation de Peter Shor, maven.smith.edu/~orourke/TOPP/P56.html apparaît, ce qui est intéressant. Cependant, il semble se concentrer sur les polygones simples généraux (c'est-à-dire qu'ils peuvent être concaves).
Raphael

Réponses:

12

Le problème peut être reformulé en choisissant un nombre maximum de points à l'intérieur d'un polygone convexe, de telle sorte que chaque paire d'entre eux soit à distance (sous la métrique ) au moins uns des autres (pensez simplement au centre des carrés ). Ceci est à son tour lié au même problème où l'on utilise la distance euclidienne régulière. Ceci est à son tour lié au maillage, où l'on est intéressé à diviser un polygone en régions bien comportées (c.-à-d., Vous prenez le diagramme de Voronoï des centres [voir les tessellations du centroïde Voronoï]). 1L1

Quoi qu'il en soit, une approximation est assez facile. Vous faites glisser au hasard une grille de longueur latérale . Coupez le polygone dans la grille et résolvez le problème à l'intérieur de chaque pièce d'intersection du polygone avec la grille en utilisant la force brute. Un algorithme avec le temps d'exécution devrait facilement suivre, où est le nombre de points (c.-à-d. Rectangles), et le est une fonction horrible qui ne dépend que de .O ( 1 / ϵ ) O ( M n o i s e ( ϵ ) ) M n o i s e ( ϵ ) ϵ(1ϵ)O(1/ϵ)O(Mnoise(ϵ))Mnoise(ϵ)ϵ

Sariel Har-Peled
la source
Merci. Ai-je raison de penser que même dans le cas où nous avons une limite polynomiale sur le nombre de rectangles / carrés, il n'est toujours pas clair si le problème est en P?
Raphael
1
Voici mes 2 cents de deviner / spéculer ... Ce serait surprenant si c'est en P - vous auriez besoin de montrer quelques propriétés supplémentaires de la solution optimale. Cependant, je pense qu'une preuve formelle de la dureté NP est hors de portée - le problème a trop de structure. Feder et Greene ont montré que l'agrégation des k-centres est difficile à estimer NP à l'intérieur d'un certain facteur. Je pense / spécule que leur preuve peut être utilisée pour prouver que le problème ci-dessus est NP-difficile si le polygone a des trous ...
Sariel Har-Peled
2

Ces deux articles abordent votre problème:

EG Birgin et RD Lobato, " Emballage orthogonal de rectangles identiques dans les régions convexes isotropes ", Computers & Industrial Engineering 59, pp. 595-602, 2010. 

EG Birgin, JM Martínez, FH Nishihara et DP Ronconi, " Emballage orthogonal d'articles rectangulaires dans des régions convexes arbitraires par optimisation non linéaire ", Computers & Operations Research 33, pp. 3535-3548, 2006.

 

Marcus Ritt
la source
Ces articles cherchent à résoudre le problème dans la pratique. Pour autant que je sache, la question est de savoir si le problème est connu pour être NP-difficile.
András Salamon
3
Il est assez facile de montrer que c'est en NP. Supposons que je vous donne un diagramme de l'emballage optimal qui vous indique quels carrés touchent quels côtés du polygone et quels carrés sont au-dessus / en dessous / à gauche / à droite d'autres carrés. La question de savoir si vous pouvez trouver les coordonnées d'un ensemble de carrés qui s'emballent exactement de cette façon est un programme linéaire, et vous pouvez donc vérifier qu'il s'agit d'un diagramme pour un emballage réalisable.
Peter Shor
4
Si tous les sommets de votre polygone sont des entiers (ou des rationnels), un résultat standard sur les programmes linéaires indique que vous n'avez pas besoin de plus qu'une quantité polynomiale de précision supplémentaire, et le programme linéaire peut être résolu exactement en temps polynomial. Toutes mes excuses si vous le saviez déjà, mais je ne peux pas dire à partir de votre commentaire ci-dessus - et même si vous l'avez fait, certaines personnes ne le sauront pas.
Peter Shor
2
Merci. Je le savais une fois mais c'était bon de me le rappeler. Il semble également que vous pourriez avoir un nombre exponentiel de carrés emballés dans le polygone, donc je ne suis pas sûr que vous puissiez vous permettre de tous les énumérer. Peut-être que vous pouvez faire une mise à l'échelle pour contourner cela?
Raphael
3
@Rafael: Je supposais (sans justification) que vous aviez un polynôme lié au nombre de carrés. Si vous autorisez des polygones de taille exponentielle, les choses deviennent beaucoup plus délicates.
Peter Shor
1

Peter Shor a observé qu'en redimensionnant, ce problème se posait au sujet de l'emballage des carrés d'unité dans un polygone convexe.

Edit: le reste de cette réponse ne s'applique pas, car il supprime l'exigence explicitement déclarée que les formes à emballer sont toutes de la même taille.


La question connexe NP-Dureté d'un cas particulier de problème d'emballage orthogonal mentionne un papier avec le résultat requis pour la première question:

  • Emballage des carrés dans un carré, Joseph YT. Leung, Tommy W. Tam, CS Wong, Gilbert H. Young et Francis YL Chin, Journal of Parallel and Distributed Computing 10 271–275. ( lien )

Extrait du journal:

nous montrons que le problème d'emballage carré est fortement NP-complet en réduisant le problème des 3 partitions.

Par conséquent, le problème est NP-difficile même pour le cas spécial où les rectangles à emballer sont similaires au conteneur. (Contrairement aux auteurs de cet article, je ne suis pas complètement convaincu que le problème est en NP, car les positions peuvent devoir être spécifiées avec une grande précision, ce qui peut faire en sorte que la vérification ne soit plus polynomiale dans la taille d'entrée. )

András Salamon
la source
5
En regardant le papier, il ressort des diagrammes que les carrés à emballer ne sont pas tous de taille égale.
Peter Shor
1
@Peter: Vous avez raison, cet article n'implique rien sur le problème de Raphaël.
András Salamon
0

Peut-être que ce document peut vous intéresser:

Mosaïque d'un polygone avec des rectangles par Kenyon & Kenyon dans FOCS 92.

Sylvain Peyronnet
la source
Merci. Cependant, si je comprends bien, un pavage couvre exactement le polygone. Cela ne sera presque jamais possible dans mon cas (considérons un triangle arbitraire à une orientation arbitraire) qui semble rendre mon problème d'optimisation fondamentalement différent.
Raphael
en effet, ce n'est pas le même problème, mon erreur.
Sylvain Peyronnet
0

Si le polygone dans lequel vous souhaitez emballer n'est pas nécessairement convexe, je pense que le problème devient NP-difficile. Voici une preuve très sommaire. La réduction provient d'un problème de type Planar-3-SAT. Pour chaque variable, vous pouvez avoir une place de 1,1 x 1, selon l'endroit où vous placez un carré déterminera si votre variable est vraie ou fausse. De plus, si vous quittez la zone .1 à gauche / à droite, vous pouvez déplacer deux autres carrés un peu plus à l'intérieur, ainsi que ceux derrière eux, pour éventuellement donner un autre espace libre de 0,1 ailleurs, qui ensemble affectent désormais quatre carrés et ainsi de suite. Une fois que vous avez autant de copies que d'occurrences du littéral respectif, vous connectez ces tubes au composant de clause respectif et utilisez à nouveau un gadget similaire pour vous assurer qu'au moins un des trois tubes entrants doit avoir un espace supplémentaire de 0,1.

domotorp
la source
1
Cela semble plausible. Notez que Raphaël a fourni un lien dans un commentaire maven.smith.edu/~orourke/TOPP/P56.html avec un pointeur sur un papier avec la réduction réelle.
András Salamon
Oh, je ne l'ai pas remarqué, merci.
domotorp