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

11

Entrée: Un ensemble de points dans R 3 et un entier k n .nR3kn

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

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 O ( n 4 ) , nous pouvons résoudre la version 1- dimensionnelle correspondante du problème en temps O ( n ) en utilisant un algorithme de fenêtre glissante.O(n5)O(n4)1O(n)

GMB
la source
Ne peut-on pas calculer un tableau de taille pour le nombre de points p avec p . x < x , p . y < y , p . z < z ? 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 k n 3 et devrions pouvoir obtenir un algorithme O ( k n 3 ) . n3pp.x<x,p.y<y,p.z<zkn3O(kn3)
Kaveh
k=Θ(n)n5n6n5
(1ϵ)kkO(((n/k)/ϵ2logn)O(1))k=Θ(n)

Réponses:

11

nO(n3)

1/kn/kO((n/k)3)RO(k6logn)fois. Avec une forte probabilité, l'une des cases que vous avez essayées est la case souhaitée.

O((n/k)3k6polylogn)=O(n3k3logO(1)n)

1k6(11/k)k61/k6=pO((1/p)logn)

Θ(n3)

O(n3log2n)

Sariel Har-Peled
la source
k=Θ(n)O(n3k3)O(n6)k