O problema de fecho convexo no plano.

• Processo: 06/00557-1
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de maio de 2006
• Data de Término da vigência: 30 de abril de 2007
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Marco Antônio Piteri
• Beneficiário: Renato de Jesus Manzoni
• Instituição Sede: Faculdade de Ciências e Tecnologia (FCT). Universidade Estadual Paulista (UNESP). Campus de Presidente Prudente. Presidente Prudente , SP, Brasil
• Assunto(s): Geometria computacional Análise de algoritmos
• Palavra(s)-Chave do Pesquisador: Algoritmos Aproximados | Analise De Algoritmos | Fecho Convexo | Geometria Computacional | Geometria Computacional

Resumo

O presente projeto se enquadra numa das linhas de pesquisa do Departamento de Matemática, Estatística e Computação (DEMEC) da Faculdade de Ciências e Tecnologia/UNESP – Campus de Presidente Prudente no qual o orientador está inserido, bem como no Programa de Pós-Graduação em Ciência da Computação interunidades da UNESP (strictu sensu) que está iniciando suas atividades no início do ano de 2006 e do qual o orientador também faz parte do quadro docente. Assim, pretende-se por meio deste projeto de iniciação científica que o aluno Renato de Jesus Manzoni entre em contato com estudos mais aprofundados na área de Geometria Computacional, potencializando e agregando valor a sua formação, de modo que no futuro ele possa dar continuidade aos seus estudos ao nível de Pós-Graduação na área de Ciência da Computação. Num certo sentido, a presente proposta está relacionada a projetos anteriores de IC já submetidos pelo Orientador a esta agência e que foram devidamente aprovados.Concretamente, o propósito fundamental deste projeto de IC é estudar e implementar diferentes abordagens algorítmicas existentes na literatura para o problema de fecho convexo de um conjunto de pontos no plano, bem como alguns problemas relacionados cuja solução de uma forma eficiente depende da existência da estrutura (lista de pontos) do fecho convexo. Em outras palavras, problemas em que o fecho convexo aparece como um subproblema a ser resolvido. Entre eles podemos citar: o par de pontos mais distante e a obtenção de camadas convexas simultâneas (onion layers).Dentro deste mesmo tema central temos como objetivo estudar e implementar algoritmos para obtenção do fecho convexo associado a uma linha poligonal e a um polígono simples, bem como explorar a estreita relação existente entre algoritmos para o problema de fecho convexo e algoritmos de ordenação. O estudo de algoritmos aproximados para o fecho convexo de um conjunto de pontos bidimensionais também integra este projeto.Uma outra questão que não pode ficar a margem de qualquer projeto versando sobre a temática de algoritmos geométricos está relacionada à aritmética de ponto flutuante. Problemas geométricos em geral são extremamente susceptíveis a aritmética finita, em particular o problema de fecho convexo que utiliza sobremaneira de um predicado geométrico de classificação de pontos em relação a segmentos orientados. Considerando que a correção e a robustez dos algoritmos para o problema de fecho convexo são fortemente dependentes do predicado acima, vamos utilizar abordagens de aritmética exata descritas por Shewchuck e amplamente utilizadas pela comunidade.O projeto possibilitará que o aluno estude os principais paradigmas de projeto de algoritmos utilizados em diferentes classes de problemas geométricos e em outras importantes classes de problemas computacionais, além de explorar e entender as limitações da aritmética de ponto flutuante associadas à robustez e consequentemente a correção de algoritmos geométricos. Permitirá também que o aluno descubra estreitas relações do problema estudado com outros problemas aparentemente tão distantes.Em síntese, a temática escolhida é relevante, abrangente e pode ser largamente explorada. Além de sua longa trajetória histórica, o problema de fecho convexo de um conjunto de pontos no plano está associada aos primórdios da área Geometria Computacional, reúne importantes e inúmeras variantes algorítmicas e está estreitamente relacionado com outras importantes subdivisões planares, como a triangulação de Delaunay e o diagrama de Voronoi, possuindo assim os elementos essenciais para introduzir o aluno num trabalho de iniciação cientifica neste vasto campo de pesquisa.Uma descrição pormenorizada das atividades a serem desenvolvidas pode ser observada no item Plano de Atividades, presente no corpo do projeto.