200px|thumb|Uma demonstração da varredura de Graham para encontrar um casco convexo 2D A varredura de Graham é um método de encontrar o casco convexo de um conjunto finito de pontos no plano com complexidade de tempo O(n log n). Ele recebeu esse nome em homenagem a Ronald Graham, que publicou o algoritmo original em 1972. O algoritmo encontra todos os vértices do casco convexo ordenados ao longo de sua fronteira. Ele usa uma pilha para detectar e remover concavidades na fronteira de forma eficiente.
Notas A mesma ideia básica funciona também se a entrada for classificada na coordenada x em vez do ângulo, e o casco for computado em duas etapas produzindo as partes superior e inferior do casco, respectivamente. Esta modificação foi idealizada por A. M. Andrew. Ela tem as mesmas propriedades básicas da varredura de Graham.
A descrição original de Graham envolvia a classificação em torno de um ponto interno do casco convexo, em vez de um de seus vértices. Para a mesma escolha de um ponto de pivô para o algoritmo de classificação, conectar todos os outros pontos em sua ordem de classificação em torno deste ponto, em vez de executar as etapas restantes da varredura de Graham, produz um polígono em forma de estrela, uma poligonalização da entrada.
A técnica de pilha usada na varredura de Graham é muito semelhante à do problema de todos os valores menores mais próximos, e algoritmos paralelos para todos os valores menores mais próximos também podem ser usados (como a varredura de Graham) para calcular cascos convexos de sequências ordenadas de pontos de forma eficiente..
Robustez numérica A robustez numérica é um problema a ser tratado em algoritmos que usam aritmética computacional de ponto flutuante de precisão finita. Um artigo de 2004 analisou uma estratégia incremental simples, que pode ser usada, em particular, para uma implementação da varredura de Graham. O objetivo declarado do artigo não era analisar especificamente o algoritmo, mas sim fornecer um exemplo de livro didático do que e como pode falhar devido a computações de ponto flutuante em geometria computacional. (An earlier version was reported in 2004 at ESA'2004) Mais tarde, D. Jiang e N. F. StewartD. Jiang and N. F. Stewart, Backward error analysis in computational geometry , Computational Science and Its Applications - ICCSA 2006 Volume 3980 of the series Lecture Notes in Computer Science, pp 50–59 elaboraram sobre isso e, usando a análise de erro reverso, chegaram a duas conclusões principais. A primeira é que o casco convexo é um problema bem condicionado e, portanto, pode-se esperar algoritmos que produzam uma resposta dentro de uma margem de erro razoável. Em segundo lugar, eles demonstram que uma modificação da varredura de Graham que eles chamam de Graham-Fortune (incorporando ideias de Steven Fortune para estabilidade numérica) supera os problemas de precisão finita e dados inexatos "na medida em que for possível fazê-lo".
Bibliografia Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 949–955 of section 33.3: Finding the convex hull.
Ligações externas C++ and Object Pascal Graham Scan Implementations
Categoria:Algoritmos Categoria:Teoria dos grafos