El problema de la envoltura convexa dinámica es una clase de problemas dinámicos en geometría computacional . El problema consiste en el mantenimiento, es decir, el seguimiento, de la envoltura convexa para los datos de entrada que experimentan una secuencia de cambios discretos, es decir, cuando los elementos de los datos de entrada pueden insertarse, eliminarse o modificarse. Debe distinguirse de la envoltura convexa cinética , que estudia problemas similares para puntos en movimiento continuo. Los problemas de envoltura convexa dinámica pueden distinguirse por los tipos de datos de entrada y los tipos permitidos de modificación de los datos de entrada.
Es fácil construir un ejemplo en el que la envoltura convexa contenga todos los puntos de entrada, pero después de la inserción de un único punto, la envoltura convexa se convierta en un triángulo. Y a la inversa, la eliminación de un único punto puede producir el cambio drástico opuesto del tamaño de la salida. Por lo tanto, si se requiere que la envoltura convexa se informe de la manera tradicional como un polígono, el límite inferior para la complejidad computacional del peor caso del recálculo de la envoltura convexa es , ya que este tiempo se requiere para un mero informe de la salida. Este límite inferior es alcanzable, porque varios algoritmos de envoltura convexa de propósito general se ejecutan en tiempo lineal cuando los puntos de entrada se ordenan de alguna manera y los métodos de tiempo logarítmico para el mantenimiento dinámico de datos ordenados son bien conocidos.
Este problema puede superarse eliminando la restricción en la representación de salida. Existen estructuras de datos que pueden mantener representaciones de la envoltura convexa en un tiempo por actualización mucho menor que el lineal. Durante muchos años, el mejor algoritmo de este tipo fue el de Overmars y van Leeuwen (1981), que tardaba O(log 2 n ) por actualización, pero desde entonces ha sido mejorado por Timothy M. Chan y otros.
En varias aplicaciones, la búsqueda de la envoltura convexa es un paso en un algoritmo para la solución del problema general. La representación seleccionada de la envoltura convexa puede influir en la complejidad computacional de operaciones posteriores del algoritmo general. Por ejemplo, la consulta de un punto en un polígono para un polígono convexo representado por el conjunto ordenado de sus vértices puede responderse en tiempo logarítmico, lo que sería imposible para envolturas convexas informadas por el conjunto de sus vértices sin ninguna información adicional. Por lo tanto, algunas investigaciones de algoritmos de envoltura convexa dinámica involucran la complejidad computacional de varios problemas de búsqueda geométrica con envolturas convexas almacenadas en tipos específicos de estructuras de datos. El enfoque mencionado de Overmars y van Leeuwen permite la complejidad logarítmica de varias consultas comunes.
