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

23

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?

Raphael
źródło
Pakowanie z prostokątami 1x3 jest NP-zupełne (z rotacją) i myślę, że staje się łatwe, jeśli nie zezwalamy na rotacje. Znajdź maksymalną liczbę prostokątów dla każdego wiersza (lub kolumny) i dodaj je, aby uzyskać całkowitą maksymalną liczbę upakowanych prostokątów.
Mohammad Al-Turkistany
Nie jestem pewien, czy ustalenie wymiarów na 1x3 (lub cokolwiek innego) zbytnio pomaga mojemu problemowi, prawda? Wypukły wielokąt nie musi mieć żadnych boków równoległych do osi i nadal musisz zdecydować, gdzie umieścić prostokąty. Możesz umieścić je najniżej na osi Y, a następnie wyjustować w lewo jako rozsądną heurystykę, ale możesz dość łatwo konstruować przykłady tam, gdzie nie jest to optymalne.
Raphael
9
Możesz zastosować transformację afiniczną, aby wszystkie prostokąty były . Problem jest więc równoważny z pakowaniem kwadratów. 1×1
Peter Shor,
1
@turkistany: Czy dałbyś mi referencję, która pokazuje kompletność NP dla prostokątów 1x3? Czy łatwo to zaobserwować?
Yoshio Okamoto
3
Szukając na podstawie obserwacji Petera Shora, pojawia się maven.smith.edu/~orourke/TOPP/P56.html , co jest interesujące. Wydaje się jednak, że koncentruje się na ogólnych prostych wielokątach (tzn. Mogą być wklęsłe).
Raphael

Odpowiedzi:

12

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

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ϵ)O(1/ϵ)O(Mnoise(ϵ))Mnoise(ϵ)ϵ

Sariel Har-Peled
źródło
Dzięki. Czy mam rację, myśląc, że nawet w przypadku, gdy mamy wielomian związany z liczbą prostokątów / kwadratów, nadal nie jest jasne, czy problem dotyczy P?
Raphael
1
Oto moje 2 centy zgadywania / spekulacji ... Byłoby zaskakujące, gdyby było w P - musiałbyś wykazać dodatkowe właściwości optymalnego rozwiązania. Sądzę jednak, że formalny dowód twardości NP jest poza zasięgiem - problem ma zbyt dużą strukturę. Feder i Greene wykazali, że grupowanie k-centrum jest trudne do oszacowania NP w ramach pewnego współczynnika. Myślę / spekuluję, że ich dowód może zostać wykorzystany do udowodnienia, że ​​powyższy problem jest trudny NP, jeśli wielokąt ma dziury ...
Sariel Har-Peled
2

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.

 

Marcus Ritt
źródło
Dokumenty te dotyczą praktycznego rozwiązania problemu. O ile mi wiadomo, pytanie brzmi, czy wiadomo, że problem jest trudny NP.
András Salamon,
3
Dość łatwo jest pokazać, że jest w NP. Załóżmy, że podam Ci schemat optymalnego upakowania, który mówi, które kwadraty dotykają, które boki wielokąta, a które kwadraty znajdują się powyżej / poniżej / lewej / prawej strony innych kwadratów. Pytanie, czy można znaleźć współrzędne zestawu kwadratów, które pakują się dokładnie w ten sposób, jest programem liniowym, a więc można sprawdzić, czy jest to schemat możliwego upakowania.
Peter Shor,
4
Jeśli wszystkie wierzchołki wielokąta są liczbami całkowitymi (lub wymiernymi), standardowy wynik w programach liniowych mówi, że nie potrzebujesz więcej niż wielomianu dodatkowej precyzji, a program liniowy można rozwiązać dokładnie w czasie wielomianowym. Przepraszam, jeśli już o tym wiedziałeś, ale nie mogę powiedzieć z powyższego komentarza - a nawet gdybyś wiedział, niektórzy ludzie nie.
Peter Shor,
2
Dzięki. Raz to wiedziałem, ale dobrze było mi przypomnieć. Wydaje się również, że możesz mieć wykładniczą liczbę kwadratów upakowanych w wielokącie, więc nie jestem pewien, czy możesz sobie pozwolić na ich listę. Może jest jakieś skalowanie, które możesz zrobić, aby obejść ten problem?
Raphael
3
@Rafael: Zakładałem (bez uzasadnienia), że masz wielomian związany z liczbą kwadratów. Jeśli dopuścisz wieloboki wielkości wykładniczej, sprawy stają się znacznie trudniejsze.
Peter Shor,
1

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

András Salamon
źródło
5
Patrząc na papier, ze schematów wydaje się, że wszystkie kwadraty, które mają być zapakowane, nie są jednakowej wielkości.
Peter Shor,
1
@Peter: Masz rację, ten artykuł nie sugeruje nic na temat problemu Raphaëla.
András Salamon,
0

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

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

Sylvain Peyronnet
źródło
Dzięki. Jeśli jednak dobrze rozumiem, kafelek dokładnie pokrywa wielokąt. W moim przypadku prawie nigdy nie będzie to możliwe (rozważ dowolny trójkąt o dowolnej orientacji), co wydaje się zasadniczo różnić mój problem optymalizacji.
Raphael
w rzeczy samej, to nie ten sam problem, mój błąd.
Sylvain Peyronnet,
0

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.

domotorp
źródło
1
Brzmi to realistycznie. Zauważ, że Raphaël podał link w komentarzu maven.smith.edu/~orourke/TOPP/P56.html ze wskaźnikiem do papieru z faktyczną redukcją.
András Salamon
Och, nie zauważyłem, dzięki.
domotorp