La caja más pequeña alineada al eje que contiene

Entrada: Un conjunto de puntos en y un número entero . $n$ $\mathbb{R}^3$ $k \le n$

Salida: el cuadro delimitador alineado al eje del volumen más pequeño que contiene al menos de estos puntos. $k$ $n$

Me pregunto si se conocen algoritmos para este problema. Lo mejor que se me ocurrió fue el tiempo , más o menos de la siguiente manera: fuerza bruta sobre todos los límites superiores e inferiores posibles para dos de las tres dimensiones; para cada una de estas posibilidades , podemos resolver la versión dimensional correspondiente del problema en tiempo usando un algoritmo de ventana deslizante. $O(n^5)$ $O(n^4)$ $1$ $O(n)$

cg.comp-geom GMB
fuente

¿No podemos calcular una tabla de tamaño

para el número de puntos

con

? Calcular el número de puntos y el volumen se puede hacer con un número constante de operaciones, y podemos usar programación dinámica con una tabla de tamaño

y deberíamos poder obtener un 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

Okay. En este caso, que

, realmente no puede esperar hacerlo mejor que

. Porque, hay

cuadros distintos, y al promediar el argumento (en un valor aleatorio de k) hay

cuadros que contienen exactamente k puntos. A menos que pueda usar de alguna manera el volumen para reducir el espacio de búsqueda, pero eso de alguna manera parece optimista ...

k = Θ (n)

$k=\Theta(n)$

n^{5}

$n^5$

n^{6}

$n^6$

n^{5}

$n^5$

Sariel Har-Peled

Por cierto, en su caso, puede obtener un cuadro que contiene

de los puntos, y que es más pequeño que el cuadro óptimo que contiene

puntos en

tiempo. Para

esto es esencialmente un tiempo de 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

Respuestas:

Para puntos hay cuadros vacíos, vea la introducción de este documento http://www.cs.uwm.edu/faculty/ad/maximal.pdf . Uno puede calcular estos cuadros aproximadamente esta vez (ver introducción para referencias). $n$ $O(n^3)$

Para su problema, tome una muestra aleatoria de puntos, donde todos los puntos se seleccionan con capacidad almacenamiento de . Tal muestra aleatoria tiene un tamaño (en expectativa) [y en aras de la contradicción, suponga que es]. Hay cajas vacías que tienen puntos de en sus lados, por lo anterior. Para cada cuadro, utilice una estructura de datos de búsqueda de rango ortogonal para calcular cuántos puntos contiene exactamente. Repita este proceso $1/k$ $n/k$ $O((n/k)^3)$ $R$ $O(k^6 \log n)$ veces. Con alta probabilidad, uno de los cuadros que probó es el cuadro deseado.

En general, el tiempo de ejecución de esto es . $O((n/k)^3 * k^6 * polylog n) = O(n^3 k^3 \log^{O(1)} n )$

Para ver por qué esto funciona, considere la caja óptima. Tiene 6 puntos de P en su límite. La probabilidad de que la muestra aleatoria seleccione estos seis puntos y ninguno de los puntos dentro del cuadro sea al menos $\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
fuente

k = Θ (n)

$k = \Theta(n)$

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

$O(n^3 k^3)$

O (n^{6})

$O(n^6)$

k

$k$