Novas estruturas de dados para representacao de mapas n-dimensionais.

• Processo: 05/53270-9
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de agosto de 2005
• Data de Término da vigência: 30 de novembro de 2006
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Jorge Stolfi
• Beneficiário: Arnaldo Jovanini Montagner
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Variedades topológicas Mapas Estruturas de dados Topologia
• Palavra(s)-Chave do Pesquisador: Estruturas De Dados | Mapas | Topologia | Variedades Topologicas

Resumo

Mapas multi-dimensionais são subdivisões de variedades topológicas em regiões simples. Tais mapas são estruturas essenciais para áreas como geometria computacional e computação gráfica. O objetivo deste trabalho é estudar estruturas de dados para representação de mapas topológicos multi-dimensionais e propor uma nova estrutura baseada no conceito de gemas (da sigla inglesa GEM de graph-encoded manifold). Uma estrutura baseada em gemas teria características interessantes, como simplicidade de representação, generalidade (uma única estrutura para qualquer dimensão n) e universalidade (todo mapa pode ser representado desta forma). Há, porém, certas implicações negativas na utilização de gemas para representar mapas. A principal delas é a relativa inflexibilidade imposta pela natureza das gemas sobre a manipulação local dos mapas. Um dos principais desafios deste trabalho será desenvolver um repertório de operações topológicas que permita a manipulação eficiente dos mapas representados como gemas, de modo que esta estrutura de dados seja competitiva com as demais. O trabalho proposto consistirá principalmente na especificação teórica da estrutura de dados e das operações topológicas sobre gemas, que terão seu uso ilustrado através da elaboração de algoritmos para resolução de problemas em geometria computacional. Planejamos também implementar todas as operações e algoritmos propostos. (AU)