El problema dinámico del casco convexo es una clase de problemas dinámicos en geometría computacional . El problema consiste en el mantenimiento, es decir, realizar un seguimiento, del casco convexo para los datos de entrada que sufren una secuencia de cambios discretos, es decir, cuándo se pueden insertar, eliminar o modificar elementos de datos de entrada. Debe distinguirse del casco cinético convexo , que estudia problemas similares para puntos en movimiento continuo. Los problemas dinámicos de casco convexo se pueden distinguir 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 carcasa convexa contenga todos los puntos de entrada, pero después de la inserción de un solo punto la carcasa convexa se convierte en un triángulo. Y a la inversa, la eliminación de un solo punto puede producir el cambio drástico opuesto en el tamaño de la producción. Por lo tanto, si se requiere que la carcasa convexa se informe de forma tradicional como un polígono, el límite inferior para el peor caso de complejidad computacional del nuevo cálculo de la carcasa convexa es , ya que este tiempo se requiere para un simple informe de la salida. Este límite inferior es alcanzable porque varios algoritmos de casco convexo de propósito general se ejecutan en tiempo lineal cuando los puntos de entrada están ordenados 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 sobre la representación de salida. Hay estructuras de datos que pueden mantener representaciones del casco convexo en un período de 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 requería un tiempo O(log 2 n ) por actualización, pero desde entonces Timothy M. Chan y otros lo han mejorado .
En varias aplicaciones, encontrar el casco convexo es un paso en un algoritmo para la solución del problema general. La representación seleccionada del casco convexo puede influir en la complejidad computacional de operaciones adicionales del algoritmo general. Por ejemplo, el punto en una consulta de 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 cascos convexos informados por el conjunto de sus vértices sin ninguna información adicional. Por lo tanto, algunas investigaciones sobre algoritmos dinámicos de casco convexo implican la complejidad computacional de varios problemas de búsqueda geométrica con cascos convexos almacenados 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.
