Znajdź największą kostkę zawartą w unii prostopadłościanów

18

Mam dużo prostopadłościanów w przestrzeni 3D, każda ma punkt początkowy na (x, y, z) i ma rozmiar (Lx, Ly, Lz). Zastanawiam się, jak znaleźć największą kostkę w tej przestrzeni 3D, która jest zawarta w unii prostopadłościanów. Czy istnieje na to wydajny algorytm?

Na przykład, jeśli mam następujące prostopadłościany:

  • prostopadłościan zaczynający się od (0,0,0) o rozmiarze (10,10,10),
  • prostopadłościan w (10,0,0) o rozmiarze (12,13,15),
  • prostopadłościan o (0,10,0) o rozmiarze (10,10,10),
  • prostopadłościan o (0,0,10) o rozmiarze (10,10,10), oraz
  • prostopadłościan przy (10,10,10) o rozmiarze (9,9,9).

Zatem największą kostką zawartą w połączeniu tych prostopadłościanów będzie sześcian zaczynający się od (0,0,0) o rozmiarze (19,19,19).

Bardziej ogólna wersja tego pytania:

Biorąc pod uwagę zbiór pól w , znajdź największą hipersześcian zawarty w unii pól.R dnRre

pantoffski
źródło
8
Myślę, że to lepsze pytanie ukryte: mianowicie, zważywszy unii skrzynek w , obliczyć największy hipersześcian zawarty wewnątrz Unii. Rre
Suresh Venkat
1
Czy te prostopadłościany mogą się pokrywać?
Peter Boothe
@Suresh, dziękuję za wyjaśnienie i uogólnienie pytania :) @Peter, w moim przypadku ... Nie będzie się on nakładać :)
pantoffski
2
Sposób, w jaki to zdefiniowałeś, brzmi jak boki kostek są wyrównane z osiami x, y i z. Czy tak jest, czy też kostki mogą mieć dowolną orientację? To oczywiście stanowi znaczącą różnicę w wydajności algorytmu.
Joe Fitzsimons
W moim przypadku twarz każdej prostopadłościanu jest prostopadła tylko do osi.
pantoffski

Odpowiedzi:

15

Cóż, oto pierwsza głupia odpowiedź ... Weź samolot przez każdą powierzchnię prostokątnych pudeł. Tworzy to siatkę o rozmiarze . Nie jest trudno obliczyć dla każdej takiej komórki siatki, czy to wewnątrz związku, czy na zewnątrz. Teraz z każdego wierzchołka siatki wyhoduj sześcian (mając ten wierzchołek jako wierzchołek), starając się, aby był jak największy. Robiąc to w najbardziej naiwny sposób, zajmuje to O ( n 3 log n ) czasu na wierzchołek, ale prawdopodobnie używając magii wyszukiwania zakresu ortogonalnego, powinno być możliwe, aby to zrobić w log O ( 1 ) n na wierzchołek. Więc O ( n 3O(n3))O(n3)logn)logO(1)n powinien być możliwy ...O(n3)logO(1)n)

Druga próba: oblicz związek. W tym konkretnym przypadku można to zrobić w czasie (przez zamiatanie płaszczyzn). Teraz zauważ , że wystarczy obliczyć schemat L voronoi granicy związku. Wykorzystując wynik: http://vw.stanford.edu/~vladlen/publications/vor-polyhedral.pdf , można to zrobić w czasie O ( n 2 + ε ) , dla dowolnej małej stałej ε > 0 .O(nlogn)L.O(n2)+ε)ε>0

Zerwania czas związany tu systemem będzie interesujący IMHO.O(n2))

Sariel Har-Peled
źródło
Dziękuję, sądzę, że L∞ jest jak dotąd najlepszym rozwiązaniem tego problemu. Ponieważ wcześniej robiłem L∞ dla 2D (zaimplementowane metodami opisanymi w tym dokumencie inf.usi.ch/faculty/papadopoulou/publications/ijcga01.pdf ). Obudowa 3D z tylko pudełkami nie powinna być trudna.
pantoffski
8

Rrere<0>01×1×1×n×n×n...×n hiperkuboid.

2)×2)×...×2)1×1×...×1

Joe Fitzsimons
źródło
Wyobrażam sobie, że możesz udowodnić, że jest w FNP (przynajmniej w przypadku prostopadłościanów wyrównanych do osi), uruchamiając powyższą argumentację w odwrotnej kolejności i pokazując, że każdy prostopadłościan stanowi ograniczenie, które można sprawdzić w czasie wielomianowym.
Joe Fitzsimons,