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

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. $n$ $\mathbb{R}^d$

ds.algorithms cg.comp-geom pantoffski
źródło

Myślę, że to lepsze pytanie ukryte: mianowicie, zważywszy unii skrzynek w

, obliczyć największy hipersześcian zawarty wewnątrz Unii.

R^{d}

$R^d$

Suresh Venkat

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

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:

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 czasu na wierzchołek, ale prawdopodobnie używając magii wyszukiwania zakresu ortogonalnego, powinno być możliwe, aby to zrobić w na wierzchołek. Więc $O(n^3)$ $O(n^3 \log n)$ $\log^{O(1)} n$ powinien być możliwy ... $O(n^3 \log^{O(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 voronoi granicy związku. Wykorzystując wynik: http://vw.stanford.edu/~vladlen/publications/vor-polyhedral.pdf , można to zrobić w czasie , dla dowolnej małej stałej . $O( n \log n)$ $L_\infty$ $O(n^{2+\varepsilon})$ $\varepsilon > 0$

Zerwania czas związany tu systemem będzie interesujący IMHO. $O(n^2)$

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

$R^d$ $d$ $<0$ $>0$ $1 \times 1 \times 1 \times n \times n \times n ... \times n$ hiperkuboid.

$2 \times 2 \times ... \times 2$ $1 \times 1 \times ... \times 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,