Problemas cinéticos em geometria computacional (2000)
- Authors:
- Autor USP: FREITAS, EDUARDO GARCIA DE - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Subjects: ALGORITMOS E ESTRUTURAS DE DADOS; GEOMETRIA COMPUTACIONAL
- Language: Português
- Abstract: Problemas em geometria computacional permitem a modelagem de situações do mundo físico no computador, de forma que esses problemas possam ser resolvidos eficientemente. Estudamos algoritmos e estruturas de dados para a solução de problemas de geometria computacional no âmbito cinético, ou seja, onde admitimos que os objetos geométricos (pontos, retas, polígonos, etc.) possuam movimento associado. Com isso, nos problemas cinéticos o valor dos atributos geométricos, que são propriedades geométricas de um conjunto, se altera com o passar do tempo. Nesta dissertação abordamos, no cenário cinético, o problema de se manter o máximo de um conjunto, o par de pontos mais próximo, o fecho convexo e o diagrama de Voronoi. Esses são exemplos de atributos geométricos. Para que possamos manter atributos geométricos sobre um conjunto de objetos em movimento de forma eficiente, apresentamos um modelo proposto por Basch, Guibas e Hershberger, que introduz as estruturas de dados cinéticos. Elas são compostas de uma prova da corretude de atributo sendo "animada" através do tempo. Apesar do movimento contínuo de cada objeto, o atributo somente será alterado pela ocorrência de eventos em momentos discretos no tempo. O modelo também introduz medidas para a análise do desempenho de tais estruturas sob quatro diferentes pontos de vista. Uma estrutura de dados cinética, segundo o modelo, deve ser eficiente, local, compacta e ter resposta rápida. Apresentamos também uma estratégiade implementação para as estruturas de dados cinéticas e exemplificamos sua utilização no problema do máximo
- Imprenta:
- Data da defesa: 01.12.2000
-
ABNT
FREITAS, Eduardo Garcia de. Problemas cinéticos em geometria computacional. 2000. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2000. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-122556/. Acesso em: 23 abr. 2024. -
APA
Freitas, E. G. de. (2000). Problemas cinéticos em geometria computacional (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-122556/ -
NLM
Freitas EG de. Problemas cinéticos em geometria computacional [Internet]. 2000 ;[citado 2024 abr. 23 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-122556/ -
Vancouver
Freitas EG de. Problemas cinéticos em geometria computacional [Internet]. 2000 ;[citado 2024 abr. 23 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-122556/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
