Ver registro no DEDALUS
Exportar registro bibliográfico

Problemas cinéticos em geometria computacional (2000)

  • Authors:
  • USP affiliated authors: FREITAS, EDUARDO GARCIA DE - IME
  • USP Schools: 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

  • Exemplares físicos disponíveis nas Bibliotecas da USP
    BibliotecaCód. de barrasNúm. de chamada
    IME31000005190QA758.T F866p e.2
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      FREITAS, Eduardo Garcia de; FERREIRA, Carlos Eduardo. Problemas cinéticos em geometria computacional. 2000.Universidade de São Paulo, São Paulo, 2000.
    • APA

      Freitas, E. G. de, & Ferreira, C. E. (2000). Problemas cinéticos em geometria computacional. Universidade de São Paulo, São Paulo.
    • NLM

      Freitas EG de, Ferreira CE. Problemas cinéticos em geometria computacional. 2000 ;
    • Vancouver

      Freitas EG de, Ferreira CE. Problemas cinéticos em geometria computacional. 2000 ;

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI: