Cápsula convexa

El problema de la cápsula convexa es el de, dados $n$ puntos en el plano, encontrar el menor polígono convexo que los contiene. Es fácil ver que los vértices de este polígono deben ser puntos del input, por lo cual el output del problema se pide en la forma de la secuencia de puntos que se obtienen al recorrer el perímetro del polígono en sentido antihorario, partiendo desde algún punto.

Si consideramos que las coordenadas son números reales, sobre los que únicamente podemos hacer operaciones matemáticas y comparaciones, entonces podemos mostrar que este problema es $\Omega(n\log n)$ mediante reducir el problema de ordenar al de la cápsula convexa. Para ordenar $A = \{ a_1, \ldots, a_n \}$, calculamos $n$ puntos $\{ (a_1,a_1^2), \ldots, (a_n,a_n^2) \}$.

Es fácil ver que los $n$ puntos están distribuidos en una parábola, por lo cual todos formarán parte de la cápsula convexa. Más aún, un listado en sentido antihorario de los puntos que parta del mínimo recorre, en sus primeras coordenadas, al conjunto $X$ en orden de menor a mayor. Una pasada simple sobre el output de la cápsula convexa nos permite detectar el menor elemento y a partir de él listar a todos en orden. Como la transformación del input y del output nos cuesta $\Theta(n) = o(n\log n)$, tenemos que $\Omega(n\log n)$ es una cota inferior al problema de calcular la cápsula convexa.

En realidad esta cota inferior puede refinarse si introducimos otras variables. Por ejemplo, si $h$ es el número de puntos en el output, existen algoritmos que resuelven el problema en tiempo $O(n\log h)$. Sin embargo, esto es todavía $O(n\log n)$ en el peor caso.