Plus petite boîte alignée sur l'axe contenant

Entrée: Un ensemble de points dans et un entier . $n$ $\mathbb{R}^3$ $k \le n$

Sortie: le plus petit cadre de délimitation aligné sur l'axe du volume qui contient au moins de ces points. $k$ $n$

Je me demande si des algorithmes sont connus pour ce problème. Le mieux que je pouvais penser était le temps , en gros, comme suit: force brute sur toutes les limites supérieures et inférieures possibles pour deux des trois dimensions; pour chacune de ces possibilités , nous pouvons résoudre la version dimensionnelle correspondante du problème en temps utilisant un algorithme de fenêtre glissante. $O(n^5)$ $O(n^4)$ $1$ $O(n)$

cg.comp-geom GMB
la source

Ne peut-on pas calculer un tableau de taille

pour le nombre de points

avec

? Le calcul du nombre de points et du volume peut être fait avec un nombre constant d'opérations, et nous pouvons utiliser la programmation dynamique avec une table de taille

et devrions pouvoir obtenir un algorithme

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

k = Θ (n)

$k=\Theta(n)$

n^{5}

$n^5$

n^{6}

$n^6$

n^{5}

$n^5$

(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)$

Réponses:

$n$ $O(n^3)$

$1/k$ $n/k$ $O((n/k)^3)$ $R$ $O(k^6 \log n)$ fois. Avec une forte probabilité, l'une des cases que vous avez essayées est la case souhaitée.

$O((n/k)^3 * k^6 * polylog n) = O(n^3 k^3 \log^{O(1)} n )$

$\frac{1}{k^6} ( 1-1/k)^{k-6} \approx 1/k^6 = p$ $O( (1/p) \log n)$

$\Theta(n^3)$

$O(n^3 \log^2 n)$

Sariel Har-Peled
la source

k = Θ (n)

$k = \Theta(n)$

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

$O(n^3 k^3)$

O (n^{6})

$O(n^6)$

k

$k$