Kleinste achsenausgerichtete Box, die

Eingabe: Eine Menge von Punkten in und eine ganze Zahl . $n$ $\mathbb{R}^3$ $k \le n$

Ausgabe: Der kleinste an der Volumenachse ausgerichtete Begrenzungsrahmen, der mindestens dieser Punkte enthält. $k$ $n$

Ich frage mich, ob Algorithmen für dieses Problem bekannt sind. Das Beste, was ich mir vorstellen konnte, war die -Zeit, lose wie folgt: Brute-Force über alle möglichen oberen und unteren Grenzen für zwei der drei Dimensionen; Für jede dieser -Möglichkeiten können wir die entsprechende dimensionale Version des Problems in -Zeit unter Verwendung eines Schiebefensteralgorithmus lösen . $O(n^5)$ $O(n^4)$ $1$ $O(n)$

cg.comp-geom GMB
quelle

Können wir nicht eine Tabelle der Größe berechnen

für die Anzahl der Punkte

mit

? Die Berechnung der Anzahl der Punkte und des Volumens kann mit einer konstanten Anzahl von Operationen erfolgen, und wir können die dynamische Programmierung mit einer Tabelle der Größe

und sollten in der Lage sein, einen

-Algorithmus zu erhalten.

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

Antworten:

$n$ $O(n^3)$

$1/k$ $n/k$ $O((n/k)^3)$ $R$ $O(k^6 \log n)$ mal. Mit hoher Wahrscheinlichkeit ist eine der Boxen, die Sie ausprobiert haben, die gewünschte Box.

$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
quelle

k = Θ (n)

$k = \Theta(n)$

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

$O(n^3 k^3)$

O (n^{6})

$O(n^6)$

k

$k$