Considerar o caso geral quando a entrada para o algoritmo é um conjunto finito de pontos não ordenados em um plano cartesiano. Um caso especial importante, no qual os pontos são dados na ordem de travessia da fronteira de um polígono simples, é descrito mais adiante em uma subseção separada.
Se nem todos os pontos estão na mesma linha, então seu casco convexo é um polígono convexo cujos vértices são alguns dos pontos do conjunto de entrada. Sua representação mais comum é a lista de seus vértices ordenados ao longo do limite no sentido horário ou anti-horário. Em algumas aplicações é conveniente representar um polígono convexo como uma intersecção de um conjunto de meios planos.
Limite inferior na complexidade computacionalEditar
Para um conjunto finito de pontos no plano o limite inferior na complexidade computacional de encontrar o casco convexo representado como um polígono convexo é facilmente mostrado como sendo o mesmo que para a ordenação usando a seguinte redução. Para o conjunto x 1 , … , x n {\displaystyle x_{1},}dots ,x_{n}}}
números para ordenar considere o conjunto de pontos ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {\postos,x_{1}^{2}),\postos ,(x_{n},x_{n}^{2})}
de pontos no plano. Como se encontram sobre uma parábola, que é uma curva convexa, é fácil ver que os vértices do casco convexo, quando percorridos ao longo do limite, produzem a ordem ordenada dos números x 1 , … , x n {\i1}displaystyle x_{1},{\i}dots ,x_{n}}}
. Claramente, o tempo linear é necessário para a transformação descrita dos números em pontos e depois extrair a sua ordem ordenação. Portanto, no caso geral o casco convexo de n pontos não pode ser computado mais rapidamente do que a ordenação.
O padrão Ω(n log n) limite inferior para ordenação é comprovado no modelo de computação em árvore de decisão, no qual apenas comparações numéricas mas não operações aritméticas podem ser realizadas; no entanto, neste modelo, cascos convexos não podem ser computados de forma alguma. A ordenação também requer tempo Ω(n log n) no modelo de árvore de decisão algébrica de computação, um modelo que é mais adequado para cascos convexos, e neste modelo os cascos convexos também requerem tempo Ω(n log n). Entretanto, em modelos de aritmética computadorizada que permitem que os números sejam ordenados mais rapidamente que o tempo O(n log n), por exemplo, usando algoritmos de ordenação inteira, cascos convexos planos também podem ser computados mais rapidamente: o algoritmo Graham scan para cascos convexos consiste em um único passo de ordenação seguido por uma quantidade linear de trabalho adicional.
Algoritmos sensíveis à saída ótimaEditar
Como dito acima, a complexidade de encontrar um casco convexo em função do tamanho de entrada n é menor limitado por Ω(n log n). Entretanto, a complexidade de alguns algoritmos de casco convexo pode ser caracterizada tanto em termos do tamanho de entrada n quanto do tamanho de saída h (o número de pontos no casco). Tais algoritmos são chamados de algoritmos sensíveis à saída. Eles podem ser assimptticamente mais eficientes do que os algoritmos Θ(n log n) nos casos em que h = o(n).
O limite inferior no pior caso de algoritmos de casco convexo sensíveis à saída foi estabelecido para ser Ω(n log h) no caso planar. Existem vários algoritmos que atingem esta complexidade de tempo ótima. O primeiro algoritmo foi introduzido por Kirkpatrick e Seidel em 1986 (que o chamou de “o último algoritmo de casco convexo”). Um algoritmo muito mais simples foi desenvolvido por Chan em 1996, e é chamado algoritmo de Chan.
AlgorithmsEdit
Known hull hull algoritmos convexos são listados abaixo, ordenados pela data da primeira publicação. A complexidade temporal de cada algoritmo é declarada em termos do número de pontos de entrada n e do número de pontos no casco h. Note que no pior caso h pode ser tão grande quanto n.
- Embalagem de presente, a.k.a. Jarvis march – O(nh)
Um dos algoritmos planares mais simples (embora não seja o mais eficiente em termos de tempo no pior caso). Criado independentemente por Chand & Kapur em 1970 e R. A. Jarvis em 1973. Tem complexidade de tempo O(nh), onde n é o número de pontos no conjunto, e h é o número de pontos no casco. No pior caso a complexidade é Θ(n2). - Graham scan – O(n log n)
Um algoritmo um pouco mais sofisticado, mas muito mais eficiente, publicado por Ronald Graham em 1972. Se os pontos já estão ordenados por uma das coordenadas ou pelo ângulo a um vector fixo, então o algoritmo leva o tempo O(n). - Quickhull
Criado independentemente em 1977 por W. Eddy e em 1978 por A. Bykat. Assim como o algoritmo quicksort, ele tem a complexidade temporal esperada de O(n log n), mas pode degenerar em O(n2) no pior caso. - Dividir e conquistar – O(n log n)
Outro algoritmo O(n log n), publicado em 1977 por Preparata e Hong. Este algoritmo também é aplicável ao caso tridimensional. - Cadeia monótona, também conhecido como algoritmo de Andrew – O(n log n)
Publicado em 1979 por A. M. Andrew. O algoritmo pode ser visto como uma variante do Graham scan que ordena os pontos lexicograficamente pelas suas coordenadas. Quando a entrada já está ordenada, o algoritmo leva tempo O(n). - Algoritmo de casco convexo incremental – O(n log n)
Publicado em 1984 por Michael Kallay. - Algoritmo Kirkpatrick-Seidel – O(n log h)
O primeiro algoritmo sensível à saída ideal. Ele modifica o algoritmo de dividir e conquistar usando a técnica de marriage-before-conquest e programação linear de baixa dimensão. Publicado por Kirkpatrick e Seidel em 1986. - O algoritmo de Chan – O(n log h)
Um algoritmo mais simples e sensível à saída ideal criado por Chan em 1996. Ele combina o empacotamento de presentes com a execução de um algoritmo O(n log n) (como Graham scan) em pequenos subconjuntos da entrada.
Akl-Toussaint heuristicEdit
A seguinte heurística simples é frequentemente usada como o primeiro passo em implementações de algoritmos de casco convexo para melhorar a sua performance. Ele é baseado no eficiente algoritmo de casco convexo de Selim Akl e G. T. Toussaint, 1978. A idéia é excluir rapidamente muitos pontos que de qualquer forma não fariam parte do casco convexo. Este método é baseado na seguinte idéia. Encontre os dois pontos com as coordenadas x mais baixas e mais altas, e os dois pontos com as coordenadas y mais baixas e mais altas. (Cada uma destas operações leva O(n). Estes quatro pontos formam um quadrilátero convexo, e todos os pontos que se encontram neste quadrilátero (excepto os quatro vértices inicialmente escolhidos) não fazem parte do casco convexo. Encontrar todos estes pontos que se encontram neste quadrilátero também é O(n), e assim, toda a operação é O(n). Opcionalmente, os pontos com menores e maiores somas de coordenadas x e y, assim como aqueles com menores e maiores diferenças de coordenadas x e y também podem ser adicionados ao quadrilátero, formando assim um octógono convexo irregular, cujas partes internas podem ser descartadas com segurança. Se os pontos são variáveis aleatórias, então para uma classe estreita mas comumente encontrada de funções de densidade de probabilidade, esta etapa de pré-processamento descartável fará um algoritmo de casco convexo ser executado no tempo esperado linear, mesmo que a pior complexidade do algoritmo de casco convexo seja quadrática em n.
Problemas de casco convexo dinâmico e on-lineEditar
A discussão acima considera o caso quando todos os pontos de entrada são conhecidos com antecedência. Pode-se considerar duas outras configurações.
- Problema de casco convexo on-line: Os pontos de entrada são obtidos seqüencialmente um a um. Após cada ponto chegar à entrada, o casco convexo para o conjunto de pontos obtidos até o momento deve ser eficientemente calculado.
- Manutenção dinâmica do casco convexo: Os pontos de entrada podem ser inseridos ou excluídos sequencialmente, e o casco convexo deve ser atualizado após cada operação de inserção/eliminação.
A inserção de um ponto pode aumentar o número de vértices de um casco convexo no máximo em 1, enquanto a exclusão pode converter um casco convexo n-vertex em um n-1-vertex.
A versão on-line pode ser manipulada com O(log n) por ponto, que é assimptticamente ótimo. A versão dinâmica pode ser manipulada com O(log2 n) por operação.
PolígonoEdito simples
O casco convexo de um polígono simples é dividido pelo polígono em pedaços, um dos quais é o próprio polígono e o resto são bolsos delimitados por um pedaço da fronteira do polígono e uma única borda do casco. Embora muitos algoritmos tenham sido publicados para o problema da construção do casco convexo de um polígono simples, quase metade deles são incorretos. McCallum e Avis forneceram o primeiro algoritmo correto. Uma simplificação posterior por Graham & Yao (1983) e Lee (1983) usa apenas uma estrutura de dados de pilha única. O algoritmo deles atravessa o polígono no sentido horário, começando pelo seu vértice mais à esquerda. Como ele faz, ele armazena uma seqüência convexa de vértices na pilha, os que ainda não foram identificados como estando dentro das bolsas. Em cada passo, o algoritmo segue um caminho ao longo do polígono desde o topo da pilha até o vértice seguinte que não está em um dos dois bolsos adjacentes ao topo da pilha. Então, enquanto os dois vértices superiores da pilha junto com este novo vértice não estão na posição convexa, ele estala a pilha, antes de finalmente empurrar o novo vértice para a pilha. Quando a travessia no sentido horário atinge o ponto inicial, o algoritmo retorna a sequência de vértices da pilha como o casco.