4.3.10 AL/Algoritmos Geométricos.

Tópicos

• Segmentos de líneas: propiedades, intersecciones.
• Algoritmos de generación del polígono convexo mínimo (convex hull).

Objetivos

• Describir y dar un análisis de tiempo para al menos dos algoritmos para obtención del polígono convexo mínimo (convex hull).
• Justificar la cota inferior $\Omega(N log N)$ para encontrar el polígono convexo mínimo (convex hull).
• Describir adicionalmente al menos un algoritmo geométrico computacional eficiente, tal como el de encontrar el par más cercano de puntos, capas convexas o capas máximas.