Algoritmo de Kirkpatrick

Construcción de un casco convexo usando el método "divide y vencerás" - un algoritmo para construir un casco convexo .

Descripción

Dado un conjunto de puntos. $S$ $norte$

Si ( es un número entero pequeño), construya un casco convexo utilizando uno de los métodos conocidos y deténgase; de lo contrario, vaya al paso 2. ${\displaystyle N\leq N_{0))$ $N_{0}$
Dividamos el conjunto original arbitrariamente en dos subconjuntos de aproximadamente el mismo tamaño y ( que contenga puntos y que contenga puntos). $S$ $S_{1}$ $S_{2}$ $S_{1}$ ${\ estilo de visualización N/2}$ $S_{2}$ ${\ estilo de visualización NN/2}$
Encuentre recursivamente las envolventes convexas de cada uno de los subconjuntos y . $S_{1}$ $S_{2}$
Construimos la envolvente convexa del conjunto original como la envolvente convexa de la unión de dos polígonos convexos y . $CH(S_{1})$ $CH(S_{2})$

Dado que: , la complejidad de este algoritmo es la solución de la relación recursiva , donde es el tiempo de construcción de la envolvente convexa de la unión de dos polígonos convexos, cada uno de los cuales tiene vértices cercanos. Se mostrará a continuación que . $CH(S)=CH(S1\taza S2)=CH(CH(S_{1})\taza CH(S_{2}))$ $T(N)\leq 2T(N/2)+f(N)$ ${\ estilo de visualización f (N)}$ ${\ estilo de visualización N/2}$ $T(N)=O(N\log N)$

Definiciones

La línea de apoyo a un polígono convexo es una línea que pasa por algún vértice del polígono de tal manera que todos los puntos interiores del polígono se encuentran en el mismo lado de la línea . $PAGS$ $yo$ $PAGS$ $yo$

A un polígono convexo , se le pueden construir líneas de apoyo desde un punto que no le pertenece. Usamos el hecho de que la línea , donde hay algún vértice del polígono , es una línea de soporte si y solo si los bordes y se encuentran en el mismo semiplano delimitado por esta línea. Es fácil ver que, en el peor de los casos, se requiere un recorrido de los vértices del polígono para construir las líneas de soporte , es decir, se buscan en tiempo lineal. $PAGS$ $A$ ${\ Displaystyle AP_ {yo}}$ $Pi}$ $PAGS$ $PAGS$ ${\ estilo de visualización (P_{i-1},P_{i})}$ ${\ estilo de visualización (P_{i},P_{i+1})}$ $PAGS$

Implementación

Ya tenemos construidos cascos convexos y . $P_{1}$ ${\ Displaystyle P_ {2}}$

Busquemos algún punto interno del polígono (por ejemplo, el centroide de cualquiera de los tres vértices ). Tal punto será un punto interior . $A$ $P_{1}$ $P_{1}$ $A$ $CH(P_{1}\cup P_{2})$
Dos casos son posibles:
1. El punto no es un punto interior del polígono . Dibujamos dos líneas de referencia para el polígono que pasa por el punto . Estas líneas de referencia pasan por los vértices y el polígono . Todos los puntos dentro del triángulo no pertenecen al límite del casco convexo . Todos los demás puntos se ordenan por ángulo polar en relación con el punto , fusionando las dos listas ordenadas de vértices en el tiempo y luego aplicando el método transversal de Graham a la lista resultante , lo que requiere solo un tiempo lineal. $A$ ${\ Displaystyle P_ {2}}$ ${\ Displaystyle P_ {2}}$ $A$ $B$ $C$ ${\ Displaystyle P_ {2}}$ ${\ estilo de visualización ABC}$ $CH(P_{1}\cup P_{2})$ $A$ $O(N_{1})+O(N_{2})=O(N)$
2. El punto es el punto interior del polígono . Ordene los vértices de ambos polígonos alrededor del centro fusionando las dos listas ordenadas de vértices y más allá . $A$ ${\ Displaystyle P_ {2}}$ $A$ $P_{1}$ ${\ Displaystyle P_ {2}}$ ${\ estilo de visualización O (N)}$
Ahora el algoritmo de Graham se puede aplicar a la lista de vértices resultante, a excepción de la fase de clasificación de puntos por coordenadas polares, luego se ejecutará en tiempo lineal.

Ahora se obtiene la envolvente convexa de la unión de polígonos convexos . $P_{1}\taza P_{2}$

Complejidad del algoritmo

En total, las tres fases del algoritmo se completan a tiempo . Así, obtenemos la relación , cuya solución, como se sabe , es , lo que determina la complejidad del algoritmo. ${\ estilo de visualización O (N)}$ ${\ estilo de visualización f (N) = O (N)}$ $T(N)\leq 2T(N/2)+O(N)$ $T(N)=O(N\log N)$

Enlaces

http://www.cs.umd.edu/~samir/754/kshand.ps _