Pakowanie prostokątów w wypukłe wielokąty, ale bez rotacji

Interesuje mnie problem pakowania identycznych kopii (2-wymiarowych) prostokątów w wypukły (2-wymiarowy) wielokąt bez nakładania się. W moim problemie nie wolno obracać prostokątów i można założyć, że są one ustawione równolegle do osi. Właśnie podano wymiary prostokąta i wierzchołki wielokąta i zapytano, ile identycznych kopii prostokąta można upakować w wielokącie. Uważam, że jeśli wolno ci obracać prostokąty, problem ten jest trudny do rozwiązania. Co jednak wiadomo, jeśli nie możesz? A może wypukły wielokąt jest po prostu trójkątem? Czy istnieją znane algorytmy aproksymacyjne, jeśli problem jest rzeczywiście trudny NP?

Podsumowanie do tej pory (21 marca '11). Peter Shor zauważa, że ​​możemy uznać ten problem za jeden z kwadratów jednostki pakującej w wypukłym wielokącie i że problem ten występuje w NP, jeśli narzucisz wielomian związany z liczbą kwadratów / prostokątów, które mają być upakowane. Sariel Har-Peled wskazuje, że istnieje PTAS dla tej samej wielomianowo ograniczonej sprawy. Jednak ogólnie liczba upakowanych kwadratów może być wykładnicza pod względem wielkości danych wejściowych, która składa się tylko z możliwie krótkiej listy par liczb całkowitych. Następujące pytania wydają się otwarte.

Czy pełna wersja nieograniczona jest w NP? Czy istnieje wersja PTAS dla wersji bez ograniczeń? Czy przypadek wielomianowy jest ograniczony w P czy NPC? A mój osobisty faworyt, czy problem jest łatwiejszy, jeśli ograniczysz się do pakowania kwadratów jednostek w trójkąt?

Problem można przeformułować jako wybranie maksymalnej liczby punktów wewnątrz wypukłego wielokąta, tak aby każda para z nich znajdowała się w odległości (pod metryką ) co najmniej od siebie (wystarczy pomyśleć o środkach kwadratów ). To z kolei wiąże się z tym samym problemem, gdy używa się zwykłej odległości euklidesowej. Jest to z kolei związane z zazębianiem się, gdy ktoś jest zainteresowany rozbiciem wielokąta na ładnie zachowane regiony (tzn. Weźmiesz schemat Voronoi centrów [patrz teselacje Centroidal Voronoi]).$L_\infty$$1$

W każdym razie aproksymacja jest dość łatwa. Losowo przesuwasz siatkę o długości bocznej . Przypnij wielokąt do siatki i rozwiąż problem wewnątrz każdego kawałka przecięcia wielokąta z siatką za pomocą brutalnej siły. Algorytm z czasem działania powinien łatwo podążać, gdzie jest liczbą punktów (tj. Prostokątów), a to przerażająca funkcja, która zależy tylko od .O ( 1 / ϵ ) O ( M ∗ n o i s e ( ϵ ) ) M n o i s e ( ϵ ) $(1-\epsilon)$$O(1/\epsilon)$$O(M*noise(\epsilon))$$M$$noise(\epsilon)$$\epsilon$

Te dwa artykuły dotyczą twojego problemu:

EG Birgin i RD Lobato, „ Ortogonalne upakowanie identycznych prostokątów w izotropowych obszarach wypukłych ”, Computers & Industrial Engineering 59, ss. 595–602, 2010. 

EG Birgin, JM Martínez, FH Nishihara i DP Ronconi, „ Ortogonalne upakowanie prostokątnych przedmiotów w dowolnych regionach wypukłych przez optymalizację nieliniową ”, Computers & Operations Research 33, s. 3535-3548, 2006.

Peter Shor zauważył, że podczas przeskalowywania problem polega na upakowaniu kwadratów jednostek w wypukły wielokąt.

Edycja: pozostała część tej odpowiedzi nie ma zastosowania, ponieważ odrzuca wyraźnie określony wymóg, aby kształty, które mają być pakowane, były tego samego rozmiaru.

Powiązane pytanie Twardość NP szczególnego przypadku problemu pakowania ortogonalnego wymienia papier z wynikiem potrzebnym na pierwsze pytanie:

• Pakowanie kwadratów w kwadrat, Joseph YT. Leung, Tommy W. Tam, CS Wong, Gilbert H. Young i Francis YL Chin, Journal of Parallel and Distributed Computing 10 271–275. ( link )

Z papieru:

pokazujemy, że problem kwadratowego upakowania jest silnie NP-zupełny, redukując do niego problem 3-partycjonowania.

Stąd problem jest trudny do przeprowadzenia nawet w przypadku specjalnego przypadku, w którym pakowane prostokąty są podobne do pojemnika. (W przeciwieństwie do autorów tego artykułu, nie jestem do końca przekonany, że problem dotyczy NP, ponieważ pozycje mogą wymagać określenia z dużą dokładnością, co może spowodować, że weryfikacja nie będzie już wielomianowa w wielkości wejściowej. )

Może ten artykuł może Cię zainteresować:

Kafelkowanie wielokąta z prostokątami autorstwa Kenyona i Kenyona w FOCS 92.

Jeśli wielokąt, w który chcesz się spakować, niekoniecznie musi być wypukły, to myślę, że problem staje się trudny do rozwiązania. Oto bardzo szkicowy dowód. Redukcja wynika z jakiegoś problemu typu Planar-3-SAT. Do każdej zmiennej możesz przypisać 1,1 x 1 miejsce, w zależności od tego, gdzie w tym obszarze umieścisz jeden kwadrat, określi, czy twoja zmienna ma wartość fałsz. Ponadto, jeśli opuścisz obszar .1 w lewo / prawo, możesz przesunąć dwa inne kwadraty nieco więcej wewnątrz, a także te za nimi, ostatecznie dając kolejne .1 wolnego miejsca w innym miejscu, które razem wpływają teraz na cztery kwadraty i tak dalej. Po uzyskaniu tylu kopii, ile wystąpień odpowiedniego literału, należy połączyć te rury z odpowiednim składnikiem klauzuli i ponownie użyć podobnego gadżetu, aby upewnić się, że z trzech przychodzących rur co najmniej jedna musi mieć dodatkową przestrzeń .1.