Trouver un plus grand cube contenu dans l'union des cuboïdes

J'ai beaucoup de cuboïdes dans l'espace 3D, chacun a un point de départ à (x, y, z) et a une taille de (Lx, Ly, Lz). Je me demande comment trouver un plus grand cube dans cet espace 3D qui est contenu dans l'union des cuboïdes. Existe-t-il un algorithme efficace pour cela?

Par exemple, si j'ai les cuboïdes suivants:

un cuboïde commençant à (0,0,0) avec une taille (10,10,10),
un cuboïde à (10,0,0) de taille (12,13,15),
un cuboïde à (0,10,0) de taille (10,10,10),
un cuboïde à (0,0,10) de taille (10,10,10), et
un cuboïde à (10,10,10) de taille (9,9,9).

Ensuite, le plus grand cube contenu dans l'union de ces cuboïdes sera un cube commençant à (0,0,0) avec une taille (19,19,19).

Une version plus générale de cette question:

Étant donné une collection de boîtes dans , trouvez le plus grand hypercube contenu dans l'union des boîtes. $n$ $\mathbb{R}^d$

ds.algorithms cg.comp-geom pantoffski
la source

Je pense qu'il y a une meilleure question cachée à l'intérieur: à savoir, étant donné l'union des boîtes dans , calculer le plus grand hypercube contenu dans l'union.

R^{d}

$R^d$

Suresh Venkat

Ces cuboïdes peuvent-ils se chevaucher?

Peter Boothe

@Suresh, merci d'avoir clarifié et généralisé la question :) @Peter, dans mon cas ... Cela ne se chevauchera pas :)

pantoffski

De la façon dont vous avez effectué cette opération, il semble que les côtés des cubes soient alignés avec les axes x, y et z. Est-ce le cas ou les cubes peuvent-ils avoir des orientations arbitraires? Cela fait évidemment une différence significative dans l'efficacité de l'algorithme.

Joe Fitzsimons

Dans mon cas, la face de chaque cuboïde est orthogonale aux axes uniquement.

pantoffski

Réponses:

Eh bien, voici une première réponse idiote ... Prenez un avion à travers chaque face des boîtes rectangulaires. Cela forme une grille de taille . Il n'est pas difficile de calculer pour chacune de ces cellules de grille, que ce soit à l'intérieur de l'union ou à l'extérieur. Maintenant, à partir de chaque sommet de la grille, développez un cube (ayant ce sommet comme sommet) en essayant de le rendre aussi grand que possible. En le faisant de la manière la plus naïve, cela prend du temps par sommet, mais probablement en utilisant la magie de recherche de plage orthogonale, on devrait être capable de le faire en par sommet. Alors $O(n^3)$ $O(n^3 \log n)$ $\log^{O(1)} n$ devrait être possible ... $O(n^3 \log^{O(1)} n )$

Un deuxième essai: calculer le syndicat. Dans ce cas spécifique, cela peut être fait en temps (en balayant les plans). Maintenant, notez qu'il vous suffit de calculer le diagramme voronoi de la frontière de l'union. En utilisant le résultat: http://vw.stanford.edu/~vladlen/publications/vor-polyhedral.pdf , cela peut être fait en temps , pour une petite constante arbitraire . $O( n \log n)$ $L_\infty$ $O(n^{2+\varepsilon})$ $\varepsilon > 0$

Briser le temps d'exécution lié ici serait intéressant, à mon humble avis. $O(n^2)$

Sariel Har-Peled
la source

Merci monsieur, je pense aussi que L∞ est jusqu'à présent la meilleure solution à ce problème. Depuis que j'ai déjà fait le cas L∞ pour 2D (implémenté par les méthodes fournies dans cet article inf.usi.ch/faculty/papadopoulou/publications/ijcga01.pdf ). Le boîtier 3D avec seulement des boîtes ne devrait pas être très difficile.

pantoffski

La réponse à la question générale sur semble être qu'il est dur NP. La preuve est assez simple. Nous prenons simplement une instance 3SAT sur variables et associons chaque variable à une dimension. Considérez l'espace comme un espace d'affectations possibles de variables: nous ne considérons que les points entre -1 et +1 dans chaque dimesnion, et associons les emplacements avec une affectation de 0 pour cette variable et avec une affectation de 1. Chaque exclut une région donnée par $R^d$ $d$ $<0$ $>0$ $1 \times 1 \times 1 \times n \times n \times n ... \times n$ hypercuboïde.

Si l'union de ces parallélépipèdes remplit l'espace (et donc contient une cube), alors il n'y a pas d' affectation satisfaisant des variables de l'instance de 3SAT. Si toutefois le plus gros cube contenu est ou 0 (pour aucune clause), les seules autres possibilités, alors une affectation satisfaisante des variables existe. $2 \times 2 \times ... \times 2$ $1 \times 1 \times ... \times 1$

Joe Fitzsimons
la source

J'imagine que vous pouvez prouver qu'il est en FNP (au moins dans le cas des cuboïdes à axes alignés), en exécutant l'argument ci-dessus à l'envers et en montrant que tout cuboïde constitue une contrainte qui peut être vérifiée en temps polynomial.

Joe Fitzsimons