Caja mínima cinética
El cuadro mínimo cinético es una estructura de datos cinéticos para mantener el cuadro delimitador mínimo de un conjunto de puntos cuyas posiciones cambian continuamente con el tiempo. Para los puntos que se mueven en un plano, la estructura de datos de casco convexo cinético se puede utilizar como base para una estructura de datos de caja mínima cinética eficiente, compacta y receptiva.
El cuadro mínimo cinético 2D se basa en el casco convexo cinético 2D de manera similar a la estructura de datos de ancho cinético que mantiene el par de líneas paralelas de distancia mínima que tienen el punto completo establecido entre ellas. En este caso, dado que una caja consta de dos pares de líneas paralelas (que son perpendiculares entre sí), se puede hacer una analogía con la ejecución de dos problemas de ancho cinético perpendicular, y la estructura de datos debe mantener conjuntos de cuatro puntos: dos antípodas . pares que tienen líneas de apoyo perpendiculares.
En la vista dual donde un punto ( a , b ) se asigna a una línea y = a x + b, se calculan cuatro envolventes (izquierda, derecha, superior, inferior). El rango en los valores de x de un segmento de línea en uno de estos sobres corresponde al rango en las pendientes de apoyo del vértice del casco convexo correspondiente en la vista principal. Por lo tanto, un intervalo en el que los valores de x de las cuatro listas envolventes se superponen (lo que se puede obtener fusionando las listas) corresponde, en la vista principal, a un rango de pendientes en el que todas las líneas paralelas y perpendiculares a las pendientes soportan las mismas cuatro convexas. vértices del casco. El cuadro mínimo (en términos de área o perímetro) se puede calcular fácilmente para cada rango de pendiente y los cuatro vértices así soportados, y luego se puede encontrar el cuadro mínimo global minimizando estos intervalos. Este algoritmo se puede cinetizar manteniendo el casco convexo en un casco convexo cinético.estructura de datos, la combinación de las cuatro listas de sobres 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 estructuras de datos de casco convexo cinético, 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 [1] La existencia de una estructura de datos local para este problema es un problema abierto.
