Proposta da monografia
Supervisora:
Cristina Gomes Fernandes
Orientador:
Carlos Eduardo Ferreira
Aluno:
Natan Costa Lima
Tema da monografia:
Problemas de deslocamento no plano em geometria computacional.
Resumo da monografia a ser desenvolvida
Problemas de deslocamento no plano em geometria computacional tem diversas aplicações, principalmente na área de robótica.
Muitos dos problemas encontrados foram extensivamente estudados, como o problema do grafo de visibilidade, o problema do menor caminho euclidiano e
alguns problemas relacionados a galerias de arte.
Um problema clássico que surge é o problema em que o robô precisa atravessar uma galeria sem colidir com obstáculos ou
então fazer o mesmo pelo menor caminho possível. Há diversas soluções
interessantes para estes problemas e uma delas, utilizando grafo de visibilidade, será apresentada nesta monografia.
Outro problema interessante é o do vigia, Watchman route problem.
Neste problema, temos uma galeria e queremos traçar um caminho curto para que o vigia consiga enxergar toda galeria
enquanto anda por esse caminho. Se considerarmos galerias quaisquer (uma galeria pode ser representada por um polígono com buracos)
ou galerias em forma de polígonos retilineares com buracos, o problema é difícil,
mas se considerarmos polígonos retilineares simples ou polígonos simples existem algoritmos eficientes que resolvem o problema.
Objetivos do trabalho
O objetivo principal deste trabalho é fazer um estudo do problema do vigia em diversos tipos de galerias, bem como apresentar as soluções
estudadas para o problema clássico de deslocamento no plano.
Há alguns trabalhos na área com conteúdo complexo e de difícil compreensão. Queremos estudar
os algoritmos para as variantes mais fáceis do problema, implementá-los e explicar as idéias de forma
clara e simples (se for possível) para que outros alunos consigam entendê-las sem precisar estudar muito sobre geometria computacional.
Como ambição pessoal e do orientador, pretendemos fazer uma apresentação com um robô de verdade andando por alguma
galeria desenhada no chão.
Atividades já realizadas
- Foram estudados vários assuntos referentes a problemas de geometria computacional durante a iniciação científica,
como a construção do grafo de visibilidade, que conta com uma implementação e um programa para sua visualização.
- Houve um levantamento de alguns artigos e livros sobre o problema do vigia.
- Foi estudada a prova de que o problema é difícil em polígonos com buracos e polígonos retilineares com buracos.
Cronograma de atividades
| Atividade/Mês | jul | ago | set | out | nov |
| Estudar os algoritmos e formas de implementá-los |
* | * | * | | |
| Implementar os algoritmos estudados |
| * | * | * | * |
| Preparação da apresentação e o pôster |
| | | * | * |
| Escrever a parte subjetiva da monografia |
| | | * | * |
| Estudar e elaborar o texto da monografia |
* | * | * | * | * |
Estrutura esperada da monografia
A monografia será composta por duas partes, uma técnica e outra subjetiva, conforme descrito no roteiro para preparação das monografias que pode ser encontrado em
www.ime.usp.br/~cef/mac499-09/rot-monografias.
A parte técnica será dividida nos seguintes itens:
- Introdução: Apresentação inicial do texto, expondo as motivações que levaram ao tema,
os objetivos do trabalho, os problemas que serão estudados e suas aplicações.
- Conceitos e tecnologias estudadas: Nesta seção serão feitas definições de alguns conceitos relevantes
ao texto da monografia e um estudo sobre alguns trabalhos existentes sobre deslocamento no plano.
- Atividades realizadas: Descrição sobre a metodologia aplicada na realização do trabalho.
- Resultados e produtos obtidos: Apresentação dos resultados obtidos durante o estudo e entrega do programa desenvolvido durante a
iniciação científica.
- Conclusão da parte técnica da monografia.
- Bibliografia.
A parte subjetiva será dividida nos seguintes itens:
- Desafios e frustrações encontrados durante os estudos referentes ao trabalho de conclusão de curso e ao curso em si.
- Lista das disciplinas cursadas durante o curso que foram mais relevantes ao trabalho e ao aluno.
- Observações sobre a aplicação de conceitos estudados nas disciplinas do curso.
- Expectativas futuras do aluno sobre como continuar os estudos.
Referências
[1] W Chin, S Ntafos, Optimum watchman routes,
Proceedings of the second annual symposium on Computational geometry, p.24-33, June 02-04, 1986, Yorktown Heights, New York, United States
[2] M. de Berg, M. van Kreveld, M. Overmars, and O.Schwarzkopf, Computacional Geometry:
Algorithms and applications (second edition) , Springer, New York, 2005.
[3] Joseph O'Rourke, Computacional Geometry in C (second edition) , Cambridge University Press, United Kingdom, 1998.
[4] K. Mulmuley, Computacional Geometry: an Introduction through Ramdomized Algorithms., Prentice Hall, Chigago, 1998.
[5] K. Kedem, R. Livne, J.Pach, and M.Sharir,
On the union of Jordan regions and collision-free translation motion amdst polygonal obstacles, Discrete Comput. Geom. 1(1986) 59-71.
[6] K. Kedem and M.Sharir, An efficient algorithm for planning collision-free translation motion of convex polygon
object in 2-dimensional space amidst polygonal obstacles., Proceedings of the 1st Annual Symp. Comp. Geom. (1985), 75-80.