Caja mínima cinética

La caja mínima cinética es una estructura de datos cinética que mantiene el cuadro delimitador mínimo de un conjunto de puntos cuyas posiciones cambian continuamente con el tiempo. Para puntos que se mueven en un plano, la estructura de datos de la envolvente convexa cinética puede utilizarse como base para una estructura de datos de caja mínima cinética que sea adaptable, compacta y eficiente.

La caja mínima cinética bidimensional se basa en la envolvente convexa cinética bidimensional de manera similar a la estructura de datos de anchura cinética , que mantiene el par de líneas paralelas de distancia mínima que tienen todo el conjunto de puntos entre ellas. En este caso, dado que una caja consta de dos pares de líneas paralelas (que son perpendiculares entre sí), se puede establecer una analogía con la resolución de dos problemas de anchura cinética perpendiculares, y la estructura de datos necesita mantener conjuntos de cuatro puntos : dos pares antipodales que tienen líneas de soporte perpendiculares. 

En la vista dual , donde un punto ( a , b ) se mapea a una línea y = ax + b , se calculan cuatro envolventes (izquierda, derecha, superior, inferior). El rango de valores x de un segmento de línea en una de estas envolventes corresponde al rango de pendientes que soportan el vértice correspondiente de la envoltura convexa en la vista primal. Por lo tanto, un intervalo donde se superponen los valores x de las cuatro listas de envolventes (que se puede obtener al fusionar las listas) corresponde, en la vista primal, a un rango de pendientes donde todas las líneas paralelas y perpendiculares a las pendientes soportan los mismos cuatro vértices de la envoltura convexa. La caja mínima (en términos de área o perímetro) se puede calcular fácilmente para cada rango de pendientes y los cuatro vértices soportados, y luego se puede encontrar la caja mínima global minimizando sobre estos intervalos. Este algoritmo se puede cinetizar manteniendo la envoltura convexa en una estructura de datos de envoltura convexa cinética , la fusión de las cuatro listas de envoltura en una lista ordenada cinética y las cajas en una cola de prioridad cinética .

La capacidad de respuesta y la compacidad de esta estructura de datos se derivan de las de las estructuras de datos de envolvente convexa cinética, lista ordenada cinética y cola de prioridad cinética. Esto también es eficiente ya que el número de cajas mínimas combinatoriamente diferentes para n puntos es${\displaystyle O(n^{2+\epsilon }).}$^{[ 1 ]} La existencia de unalocalpara este problema es unproblema abierto.