Menor caixa alinhada ao eixo que contém pontos

Entrada: um conjunto de pontos em e um número inteiro . $n$ $\mathbb{R}^3$ $k \le n$

Saída: a menor caixa delimitadora alinhada ao eixo de volume que contém pelo menos desses pontos. $k$ $n$

Gostaria de saber se algum algoritmo é conhecido por esse problema. O melhor que pude pensar foi no tempo , da seguinte maneira: força bruta sobre todos os limites superiores e inferiores possíveis para duas das três dimensões; para cada uma dessas possibilidades , podemos resolver a versão dimensional correspondente do problema em tempo usando um algoritmo de janela deslizante. $O(n^5)$ $O(n^4)$ $1$ $O(n)$

cg.comp-geom GMB
fonte

Não podemos calcular uma tabela de tamanho para o número de pontos com ? A computação do número de pontos e do volume pode ser feita com um número constante de operações, e podemos usar a programação dinâmica com uma tabela de tamanho e devemos conseguir o algoritmo .

n^{3}

$n^3$

p

$p$

p . x < x, p . y < y, p . z < z

$p.x< x, p.y<y, p.z <z$

k n^{3}

$k n^3$

O (k n^{3})

$O(kn^3)$

Kaveh

Está bem. Nesse caso, que , você não pode realmente esperar fazer melhor que . Porque, existem caixas distintas diferentes e, pelo argumento da média (em um valor aleatório de k), existem caixas contendo exatamente k pontos. A menos que você pode de alguma forma usar a coisinha de volume de alguma forma smallify o espaço de busca, mas que de alguma forma parece otimista ...

k = Θ (n)

$k=\Theta(n)$

n^{5}

$n^5$

n^{6}

$n^6$

n^{5}

$n^5$

Sariel Har-Peled

BTW, no seu caso, você pode obter uma caixa contendo dos pontos, e que é menor que a caixa ideal que contém pontos em tempo. Para isto é, essencialmente, o tempo polylog, ...

(1 - ϵ) k

$(1-\epsilon)k$

k

$k$

O (((n / k) / ϵ^{2} \log n)^{O (1)})

$O( ((n/k)/\epsilon^2 \log n)^{O(1)})$

k = Θ (n)

$k = \Theta(n)$

Sariel Har-Peled

Respostas:

Para pontos, existem caixas vazias, consulte a introdução deste documento http://www.cs.uwm.edu/faculty/ad/maximal.pdf . Pode-se calcular essas caixas aproximadamente dessa vez (consulte a introdução para refs). $n$ $O(n^3)$

Para o seu problema, pegue uma amostra aleatória de pontos, onde cada ponto é escolhido com capacidade de . Uma amostra tão aleatória tem tamanho (na expectativa) [e, por uma questão de contradição, assuma que seja]. Existem caixas vazias com pontos de ao lado, acima. Para cada caixa, use um intervalo ortogonal pesquisando a estrutura de dados para calcular quantos pontos exatamente ela contém. Repita este processo vezes. Com alta probabilidade, uma das caixas que você tentou é a caixa desejada. $1/k$ $n/k$ $O((n/k)^3)$ $R$ $O(k^6 \log n)$

No geral, o tempo de execução disso é . $O((n/k)^3 * k^6 * polylog n) = O(n^3 k^3 \log^{O(1)} n )$

Para ver por que esse trabalho, considere a caixa ideal. Tem 6 pontos de P no seu limite. A probabilidade de a amostra aleatória escolher esses seis pontos e nenhum dos pontos dentro da caixa ser pelo menos . Assim, se você repetir o processo vezes, com alta probabilidade, uma das amostras aleatórias induzirá a caixa desejada como uma caixa vazia. $\frac{1}{k^6} ( 1-1/k)^{k-6} \approx 1/k^6 = p$ $O( (1/p) \log n)$

Como é restrito para o número de caixas vazias (consulte o artigo acima para obter referências relevantes), parece improvável que seja possível um algoritmo significativamente mais rápido. $\Theta(n^3)$

[Na ref que eu dei, eles mencionam que [17] fornece um algoritmo que enumera todas as caixas vazias máximas entre os pontos em 3d no tempo , que é a caixa preta que você precisa para os itens acima. .] $O(n^3 \log^2 n)$

Sariel Har-Peled
fonte

k = Θ (n)

$k = \Theta(n)$

O (n^{3} k^{3})

$O(n^3 k^3)$

O (n^{6})

$O(n^6)$

k

$k$