| Título: | Sweep line : um paradigma para solução de problemas de geometria computacional |
| Autor(es): | Silva, Sara Conceição de Sousa Araújo |
| Orientador(es): | Costa Júnior, Edson Alves da |
| Assunto: | Sweep line
Geometria computacional
Algoritmos de varredura |
| Data de apresentação: | 3-Nov-2021 |
| Data de publicação: | 30-Mai-2022 |
| Referência: | SILVA, Sara Conceição de Sousa Araújo. Sweep line: um paradigma para solução de problemas de geometria computacional. 2021. 97 f., il. Trabalho de conclusão de curso (Bacharelado em Engenharia de Software) — Universidade de Brasília, Brasília, 2021. |
| Resumo: | O número de iniciativas que promovem competições de programação vem crescendo cada vez mais, incentivando profissionais de tecnologia na aquisição e aperfeiçoamento de habilidades técnicas. Os problemas a serem resolvidos nessas maratonas podem ter a seguinte categorização, dentre outras: Geometria Computacional, Força Bruta, AdHoc, Programação Dinâmica, String, Matemática e Grafos. O presente trabalho tem o objetivo de implementar e analisar algoritmos de Geometria Computacional utilizando a técnica de sweep line voltada para maratonas de programação. A análise dos algoritmos foi feita seguindo os requisitos de viabilidade de uso em competições de programação: baixa complexidade de tempo e fácil implementação. Foram analisados os seguintes algoritmos: pontos de interseção de segmentos de reta, par de pontos mais próximos, envoltório convexo de Graham e de Andrew. O trabalho mostra que as soluções apresentadas com sweep line são, na maioria dos casos, viáveis de serem usadas em maratonas. |
| Abstract: | The number of initiatives promoting programming competitions has been growing more and more, encouraging technology professionals to acquire and improve technical skills. The problems to be solved in these marathons can have the following categorization, among others: Computational Geometry, Brute Force, AdHoc, Dynamic Programming, String, Mathematics and Graphs. This work aims to implement and analyze computational geometry algorithms using the sweep line technique aimed at programming marathons. The algorithms’ analysis was performed following the requirements of the feasibility of usage in programming competitions: low execution time complexity and easy implementation. The following algorithms were analyzed: line segments’ intersection
points, pair closest points, Graham’s and Andrew’s convex hull. The work shows that the sweep line solutions are, in most cases, feasible to be used in programming contests. |
| Informações adicionais: | Trabalho de conclusão de curso (graduação) — Universidade de Brasília, Faculdade UnB Gama, Engenharia de Software, 2021. |
| Licença: | A concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor que autoriza a Biblioteca Digital da Produção Intelectual Discente da Universidade de Brasília (BDM) a disponibilizar o trabalho de conclusão de curso por meio do sítio bdm.unb.br, com as seguintes condições: disponível sob Licença Creative Commons 4.0 International, que permite copiar, distribuir e transmitir o trabalho, desde que seja citado o autor e licenciante. Não permite o uso para fins comerciais nem a adaptação desta. |
| Aparece na Coleção: | Engenharia de Software
|
Todos os itens na BDM estão protegidos por copyright. Todos os direitos reservados.
