Varredura de Graham

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.[1] 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.[2] Ela tem as mesmas propriedades básicas da varredura de Graham.[3]

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.[1] 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.[4]

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.[5]

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.[6] 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.[6] Mais tarde, D. Jiang e N. F. Stewart[7] 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[8]) supera os problemas de precisão finita e dados inexatos "na medida em que for possível fazê-lo".

Referências

  1. ↑ a b Graham, R.L. (1972). «An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set» (PDF). Information Processing Letters. 1 (4): 132–133. doi:10.1016/0020-0190(72)90045-2 
  2. ↑ Andrew, A. M. (1979). «Another efficient algorithm for convex hulls in two dimensions». Information Processing Letters. 9 (5): 216–219. doi:10.1016/0020-0190(79)90072-3 
  3. ↑ De Berg, Mark; Cheong, Otfried; Van Kreveld, Marc; Overmars, Mark (2008). Computational Geometry Algorithms and Applications. Berlin: Springer. pp. 2–14. ISBN 978-3-540-77973-5. doi:10.1007/978-3-540-77974-2 
  4. ↑ Arkin, Esther M.; Fekete, Sándor P.; Hurtado, Ferran; Mitchell, Joseph S. B.; Noy, Marc; Sacristán, Vera; Sethia, Saurabh (2003). «On the reflexivity of point sets». In: Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha. Discrete and Computational Geometry: The Goodman-Pollack Festschrift. Algorithms and Combinatorics. 25. Berlin: Springer. pp. 139–156. ISBN 978-3-642-62442-1. MR 2038472. doi:10.1007/978-3-642-55566-4_6 
  5. ↑ Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993). «Optimal double logarithmic parallel algorithms based on finding all nearest smaller values». Journal of Algorithms. 14 (3): 344–370. CiteSeerX 10.1.1.55.5669Acessível livremente. doi:10.1006/jagm.1993.1018 .
  6. ↑ a b Kettner, Lutz; Mehlhorn, Kurt; Pion, Sylvain; Schirra, Stefan; Yap, Chee (2008). «Classroom examples of robustness problems in geometric computations» (PDF). Computational Geometry. 40 (1): 61–78. doi:10.1016/j.comgeo.2007.06.003Acessível livremente  (An earlier version was reported in 2004 at ESA'2004)
  7. ↑ D. Jiang and N. F. Stewart, Backward error analysis in computational geometry Arquivado em 2017-08-09 no Wayback Machine, Computational Science and Its Applications - ICCSA 2006 Volume 3980 of the series Lecture Notes in Computer Science, pp 50–59
  8. ↑ Fortune, Steven (1989). «Stable maintenance of point set triangulations in two dimensions» (PDF). 30th Annual Symposium on Foundations of Computer Science. 30. [S.l.: s.n.] pp. 494–499. ISBN 0-8186-1982-1. doi:10.1109/SFCS.1989.63524. Cópia arquivada (PDF) em 28 de julho de 2013 

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

Este artigo é emitido por Wikipédia. O texto é licenciado sob Creative Commons Attribution-Share Alike 4.0. Termos adicionais podem ser aplicados aos arquivos de mídia.