El algoritmo de Timothy Chan para calcular cierres convexos

Ponente(s): David Merinos Sosa, Dra. Dolores Lara
Un subconjunto $S$ es llamado convexo si y sólo si para todo par de puntos $p,q \in S$ el segmento $pq$ está completamente contenido en $S$. El cierre convexo, $CH(\cdot)$, de un conjunto $S$ es el convexo más pequeño que contiene a $S$. En la geometría computacional existen diversos algoritmos para calcular el cierre convexo de un conjunto de puntos. En dos dimensiones, hay diversos algoritmos que tienen complejidad $O(n \log n)$, por ejemplo el algoritmo conocido como ‘Graham’s Scan’ y el algoritmo de Preparata y Hong; estos algoritmos son óptimos en el peor caso. Sin embargo, si el número h de vértices en el cierre convexo es pequeño entonces es posible obtener mejores tiempos. El algoritmo Jarvis March logra esto con un tiempo de $O(nh)$, esta complejidad fue mejorada por Kirkpatrick y Seidel que dieron un algoritmo con complejidad de $O(n \log h)$. En este poster explicaré el algoritmo de T. M. Chan que tiene complejidad de $O(n lg h)$ y que es mucho más simple que el algoritmo de Kirkpatrick y Seidel.