Algoritmo de Kirkpatrick-Seidel
El algoritmo de Kirkpatrick-Seidel , propuesto por sus autores como un posible "algoritmo de casco convexo plano final", es un algoritmo para calcular el casco convexo de un conjunto de puntos en el plano, con complejidad de tiempo , donde es el número de puntos de entrada y es el número de puntos (puntos no dominados o máximos, como se llama en algunos textos) en el casco. Por lo tanto, el algoritmo es sensible a la salida : su tiempo de ejecución depende tanto del tamaño de entrada como del tamaño de salida. Otro algoritmo sensible a la salida, el algoritmo de envoltura de regalos. , se conocía mucho antes, pero el algoritmo Kirkpatrick-Seidel tiene un tiempo de ejecución asintótico que es significativamente menor y que siempre mejora en los límites de los algoritmos no sensibles a la salida. El algoritmo Kirkpatrick-Seidel lleva el nombre de sus inventores, David G. Kirkpatrick y Raimund Seidel . [1]
Aunque el algoritmo es asintóticamente óptimo, no es muy práctico para problemas de tamaño moderado. [2]
La idea básica del algoritmo es una especie de inversión del algoritmo divide y vencerás para los cascos convexos de Preparata y Hong, apodado "matrimonio antes de la conquista" por los autores.
El algoritmo tradicional de dividir y conquistar divide los puntos de entrada en dos partes iguales, por ejemplo, mediante una línea vertical, encuentra recursivamente cascos convexos para los subconjuntos izquierdo y derecho de la entrada y luego fusiona los dos cascos en uno al encontrar el " bordes del puente ", bitangentes que conectan los dos cascos desde arriba y desde abajo.
El algoritmo de Kirkpatrick-Seidel divide la entrada como antes, al encontrar la mediana de las coordenadas x de los puntos de entrada. Sin embargo, el algoritmo invierte el orden de los pasos siguientes: su siguiente paso es encontrar los bordes del casco convexo que se cruzan con la línea vertical definida por esta coordenada x mediana, que resulta requerir un tiempo lineal. [3]Los puntos en los lados izquierdo y derecho de la línea de división que no pueden contribuir al eventual casco se descartan y el algoritmo procede de forma recursiva en los puntos restantes. Más detalladamente, el algoritmo realiza una recursividad separada para las partes superior e inferior del casco convexo; en la recursividad para el casco superior, los puntos que no contribuyen a ser descartados son aquellos debajo del borde del puente verticalmente, mientras que en la recursividad para el casco inferior se descartan los puntos por encima del borde del puente verticalmente.