Envolvente convexa
La forma convexa más pequeña que encierra un conjunto de puntos — imagina una goma elástica tensada en torno a unos clavos sobre una tabla.
Los algoritmos clásicos son Graham scan (1972), gift wrapping (marcha de Jarvis, 1973), QuickHull y el algoritmo de Chan, que alcanza el óptimo O(n log h). En 2D la envolvente entera es un polígono; en 3D, un poliedro.
En juegos y física, las formas de colisión se construyen a menudo como la envolvente convexa de un modelo, porque el test convexo-contra-convexo mediante GJK es barato y robusto. Los modelos cóncavos se descomponen primero con descomposición convexa.