Encontre um cubo maior contido na união de cuboides

Eu tenho muitos cuboides no espaço 3D, cada um tem um ponto de partida em (x, y, z) e tem tamanho de (Lx, Ly, Lz). Gostaria de saber como encontrar um cubo maior neste espaço 3D que está contido na união dos cuboides. Existe um algoritmo eficiente para isso?

Por exemplo, se eu tiver os seguintes cuboids:

um cubóide com início em (0,0,0) com tamanho (10,10,10),
um cubóide em (10,0,0) com tamanho (12,13,15),
um cubóide em (0,10,0) com tamanho (10,10,10),
um cubóide em (0,0,10) com tamanho (10,10,10), e
um cubóide em (10,10,10) com tamanho (9,9,9).

Então, o maior cubo contido na união desses cubóides será um cubo começando em (0,0,0) com tamanho (19,19,19).

Uma versão mais geral desta pergunta:

Dado um conjunto de caixas em , encontrar o maior hypercube contido dentro da união das caixas. $n$ $\mathbb{R}^d$

ds.algorithms cg.comp-geom pantoffski
fonte

Eu acho que há uma pergunta melhor escondido dentro: a saber, dada a união de caixas em

, calcular o maior hypercube contido dentro da união.

R^{d}

$R^d$

Suresh Venkat

Esses cubóides podem se sobrepor?

precisa

@Suresh, obrigado por esclarecer e generalizar a questão :) @ Pedro, no meu caso ... Não vai sobreposição :)

pantoffski

Do jeito que você colocou isso, parece que os lados dos cubos estão alinhados com os eixos x, ye z. É esse o caso ou os cubos podem ter orientações arbitrárias? Obviamente, isso faz uma diferença significativa na eficiência do algoritmo.

Joe Fitzsimons

No meu caso, a face de cada cubóide é ortogonal apenas aos eixos.

pantoffski

Respostas:

Bem, aqui está uma primeira tentativa de resposta tola ... Pegue um avião através de cada face das caixas retangulares. Forma uma grade de tamanho . Não é difícil calcular para cada célula da grade, seja dentro ou fora da união. Agora, a partir de cada vértice da grade, aumente um cubo (tendo esse vértice como um vértice) tentando torná-lo o maior possível. Fazendo isso da maneira mais ingênua, isso leva tempo por vértice, mas provavelmente usando magia de busca de faixa ortogonal, deve-se ser capaz de fazê-lo no por vértice. Então $O(n^3)$ $O(n^3 \log n)$ $\log^{O(1)} n$ deve ser possível ... $O(n^3 \log^{O(1)} n )$

Uma segunda tentativa: calcule a união. Nesse caso específico, isso pode ser feito no tempo (varrendo os planos). Agora, observe que você só precisa calcular o diagrama de voronoi dos limites da união. Usando o resultado: http://vw.stanford.edu/~vladlen/publications/vor-polyhedral.pdf , isso pode ser feito no tempo , para uma constante pequena e arbitrária . $O( n \log n)$ $L_\infty$ $O(n^{2+\varepsilon})$ $\varepsilon > 0$

Quebrar o tempo de execução vinculado aqui seria interessante, IMHO. $O(n^2)$

Sariel Har-Peled
fonte

Obrigado senhor, também acho que L∞ é a melhor solução para esse problema até agora. Desde que eu fiz o caso L∞ para 2D antes (implementado pelos métodos fornecidos neste artigo inf.usi.ch/faculty/papadopoulou/publications/ijcga01.pdf ). O gabinete 3D com apenas caixas não deve ser muito difícil.

pantoffski

$R^d$ $d$ $<0$ $>0$ $1 \times 1 \times 1 \times n \times n \times n ... \times n$ hipercubóide.

$2 \times 2 \times ... \times 2$ $1 \times 1 \times ... \times 1$

Joe Fitzsimons
fonte

Imagino que você possa provar que está no FNP (pelo menos no caso de cuboides alinhados por eixos), executando o argumento acima em sentido inverso e mostrando que qualquer cubóide constitui uma restrição que pode ser verificada em tempo polinomial.

21811 Joe Fitzsimons