Finde einen größten Würfel in der Vereinigung der Quader

Ich habe viele Quader im 3D-Raum, jeder hat einen Startpunkt bei (x, y, z) und eine Größe von (Lx, Ly, Lz). Ich frage mich, wie man einen größten Würfel in diesem 3D-Raum findet, der in der Vereinigung der Quader enthalten ist. Gibt es dafür einen effizienten Algorithmus?

Zum Beispiel, wenn ich die folgenden Quader habe:

ein Quader ab (0,0,0) mit der Größe (10,10,10),
ein Quader bei (10,0,0) mit der Größe (12,13,15),
ein Quader bei (0,10,0) mit der Größe (10,10,10),
ein Quader bei (0,0,10) mit der Größe (10,10,10) und
ein Quader bei (10,10,10) mit der Größe (9,9,9).

Dann ist der größte Würfel, der in der Vereinigung dieser Quader enthalten ist, ein Würfel, der bei (0,0,0) mit der Größe (19,19,19) beginnt.

Eine allgemeinere Version dieser Frage:

Suchen Sie bei einer gegebenen Sammlung von Boxen in den größten Hypercube, der in der Vereinigung der Boxen enthalten ist. $n$ $\mathbb{R}^d$

ds.algorithms cg.comp-geom pantoffski
quelle

Ich denke, dass sich darin eine bessere Frage verbirgt: Berechnen Sie bei einer Vereinigung von Feldern in

R^{d}

$R^d$ den größten in der Vereinigung enthaltenen Hypercube.

Suresh Venkat

Können sich diese Quader überlappen?

Peter Boothe

@ Suresh, danke für die Klärung und Verallgemeinerung der Frage :) @ Peter, in meinem Fall ... Es wird nicht überlappen :)

Pantoffski

So wie Sie dies phasenweise eingestellt haben, klingt es so, als ob die Seiten der Würfel an den x-, y- und z-Achsen ausgerichtet sind. Ist dies der Fall oder können die Würfel beliebige Ausrichtungen haben? Dies macht offensichtlich einen signifikanten Unterschied für die Effizienz des Algorithmus.

Joe Fitzsimons

In meinem Fall ist die Fläche jedes Quaders nur orthogonal zu den Achsen.

Pantoffski

Antworten:

Nun, hier ist eine erste dumme Antwort ... Nimm ein Flugzeug durch jede Seite der rechteckigen Kisten. Diese bilden ein Raster der Größe . Es ist nicht schwer, für jede solche Gitterzelle zu berechnen, ob sie sich innerhalb oder außerhalb der Union befindet. Wachsen Sie nun aus jedem Gitterpunkt einen Würfel (mit diesem Punkt als Punkt), um ihn so groß wie möglich zu machen. Wenn Sie dies auf die naivste Art und Weise tun, dauert dies Zeit pro Scheitelpunkt, aber wahrscheinlich mit orthogonaler Entfernungssuchmagie sollte es möglich sein, dies in pro Scheitelpunkt zu tun . Also $O(n^3)$ $O(n^3 \log n)$ $\log^{O(1)} n$ sollte möglich sein ... $O(n^3 \log^{O(1)} n )$

Ein zweiter Versuch: Berechnen Sie die Vereinigung. In diesem speziellen Fall kann dies in Zeit (durch Kehren von Ebenen) erfolgen. Beobachten Sie nun, dass Sie nur das voronoi-Diagramm der Grenze der Vereinigung berechnen müssen . Mit dem Ergebnis: http://vw.stanford.edu/~vladlen/publications/vor-polyhedral.pdf kann dies in für eine beliebige kleine Konstante . $O( n \log n)$ $L_\infty$ $O(n^{2+\varepsilon})$ $\varepsilon > 0$

Es wäre interessant, die hier festgelegte -Laufzeit zu durchbrechen, IMHO. $O(n^2)$

Sariel Har-Peled
quelle

Vielen Dank, Sir. Ich denke auch, dass L∞ die beste Lösung für dieses Problem ist. Da ich den L∞ für 2D-Fall bereits durchgeführt habe (implementiert mit den in diesem Artikel beschriebenen Methoden inf.usi.ch/faculty/papadopoulou/publications/ijcga01.pdf ). Das 3D-Gehäuse mit nur Boxen dürfte nicht allzu schwierig sein.

Pantoffski

Die Antwort auf die allgemeine Frage zu scheint zu sein, dass es NP-schwer ist. Der Beweis ist ziemlich einfach. Wir nehmen einfach eine 3SAT-Instanz für Variablen und ordnen jeder Variablen eine Dimension zu. Stellen Sie sich den Raum als einen Raum möglicher Zuweisungen von Variablen vor: Wir betrachten nur Punkte zwischen -1 und +1 in jeder Dimension und ordnen Positionen einer Zuweisung von 0 für diese Variable und einer Zuweisung von 1 zu Klausel schließt einen Bereich aus, der durch $R^d$ $d$ $<0$ $>0$ $1 \times 1 \times 1 \times n \times n \times n ... \times n$ hyperkuboid.

Wenn die Vereinigung dieser Quader den Raum füllt (und so enthält einen Würfel), dann gibt es keine befriedigende Zuordnung von Variablen für die 3SAT Instanz. Wenn jedoch der größte enthaltene Würfel oder 0 (für keine Klauseln), die einzigen anderen Möglichkeiten, dann besteht eine zufriedenstellende Zuordnung von Variablen. $2 \times 2 \times ... \times 2$ $1 \times 1 \times ... \times 1$

Joe Fitzsimons
quelle

Ich stelle mir vor, Sie können dies in FNP (zumindest im Fall von mit Achsen ausgerichteten Quadern) beweisen, indem Sie die obige Argumentation in umgekehrter Reihenfolge ausführen und zeigen, dass jeder Quader eine Beschränkung darstellt, die in der Polynomzeit überprüft werden kann.

Joe Fitzsimons