Definición
Un método o algoritmo para encontrar el conjunto convexo más pequeño (envolvente convexa) que contiene un conjunto finito de puntos; la envolvente convexa es el polígono o politopo convexo mínimo que encierra los puntos y es un primitivo geométrico básico.
Principio
Principio
La envolvente convexa puede caracterizarse como la intersección de todos los conjuntos convexos que contienen los puntos o, equivalentemente, como el conjunto de todas las combinaciones convexas de los puntos; los métodos computacionales explotan puntos extremos, ordenación por ángulo, inserción incremental o divide y vencerás para producir los vértices de la envolvente.
Demostración
Demostración
Para puntos en el plano, se puede calcular la envolvente encontrando primero un vértice extremo, ordenando los demás puntos por ángulo polar alrededor de él y realizando un barrido con pila que descarta puntos interiores para producir la secuencia de vértices que forman el polígono convexo de la envolvente.
Aplicación incorrecta
Aplicación incorrecta
Usar comprobaciones geométricas ingenuas O(n^2) o no manejar colinealidades y precisión numérica puede producir envolventes incorrectas (vértices extremos ausentes o puntos interiores incluidos) u órdenes de vértices inestables para procesos posteriores.
Consecuencia
Consecuencia
La construcción correcta de la envolvente convexa produce un encierro convexo mínimo útil para detección de colisiones, aproximación de forma, cálculo de diámetro y anchura, y como paso de preprocesamiento en muchos algoritmos geométricos, reduciendo frecuentemente la complejidad del problema.
Inversión
Inversión
La noción dual es el núcleo convexo o la intersección de semiespacios de soporte de un polígono; invertir el foco desde el superconjunto convexo mínimo a subconjuntos convexos máximos o núcleos esclarece problemas complementarios de factibilidad y visibilidad.
Límite
Límite
Se aplica a conjuntos finitos de puntos en el espacio euclídeo y se generaliza a dimensiones superiores como politopos convexos; excluye conjuntos infinitos sin supuestos de compacidad y requiere cuidado en geometrías no euclídeas o con configuraciones degeneradas colineales/coplanares.
Tensión semántica
Tensión semántica
La envolvente convexa a veces se confunde con cajas envolventes u otras figuras de contorno; a diferencia de cajas alineadas a ejes o rectángulos de área mínima, la envolvente convexa es el conjunto convexo más pequeño y puede tener un número arbitrario de vértices según la distribución de los puntos.
Síntesis
Síntesis
La construcción de la envolvente convexa calcula el superconjunto convexo mínimo de un conjunto de puntos identificando vértices extremos y ordenándolos para formar un politopo convexo; esto reduce muchos problemas geométricos a operaciones sobre una estructura combinatoria más pequeña que captura la geometría exterior del conjunto.